// Copyright (c) 2008 Tony Garnock-Jones <tonyg@lshift.net>
// Copyright (c) 2008 LShift Ltd. <query@lshift.net>
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation files
// (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software,
// and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

var Dvcs = {
    _debugMode: false,

    Util: {
        random_hex_string: function(n) {
            var digits = "0123456789abcdef";
            var result = "";
            for (var i = 0; i < n; i++) {
                result = result + digits[Math.floor(Math.random() * 16)];
            }
            return result;
        },

        random_uuid: function() {
            if (Dvcs._debugMode) {
                return Dvcs.Util.random_hex_string(8);
            } else {
                return [Dvcs.Util.random_hex_string(8),
                        Dvcs.Util.random_hex_string(4),
                        "4" + Dvcs.Util.random_hex_string(3),
                        ((Math.floor(Math.random() * 256) & ~64) | 128).toString(16) +
                        Dvcs.Util.random_hex_string(2),
                        Dvcs.Util.random_hex_string(12)].join("-");
            }
        },

        dict_union: function(s1, s2) {
            var result = {};
            var k;
            for (k in s2) { result[k] = s2[k]; }
            for (k in s1) { result[k] = s1[k]; }
            return result;
        },

        dict_difference: function(s1, s2) {
            var result = {};
            var k;
            for (k in s1) { result[k] = s1[k]; }
            for (k in s2) { delete result[k]; }
            return result;
        },

        dict_to_set: function(d) {
	    var result = {};
            for (var k in d) { result[k] = 1; }
            return result;
        },

        deepCopy: function(obj) {
            // Courtesy of
            // http://keithdevens.com/weblog/archive/2007/Jun/07/javascript.clone
            //
            // Does not handle recursive structures.

            if (obj === null || typeof(obj) != 'object') {
                return obj;
            }

            var temp = obj.constructor();
            for (var key in obj) {
                temp[key] = Dvcs.Util.deepCopy(obj[key]);
            }
            return temp;
        }
    },

    Mergers: {
        simpleScalarMerger: function(v1, v0, v2) {
            if (v1 == v2) return [{ok: v1}];
            if (v1 == v0) return [{ok: v2}];
            if (v2 == v0) return [{ok: v1}];
            return [{conflict: {a: v1, o: v0, b: v2}}];
        },

        simpleTextualMerger: function(v1, v0, v2) {
            return Diff.diff3_merge(v1, v0, v2, true);
        },

        Defaults: {}
    },

    Checkout: function(directParent, additionalParent, currentBranch) {
        this.inodes = {};
        this.directParent = directParent;
        this.additionalParent = additionalParent;
        this.dirty = {};
	this.anyDirty = false;
        this.currentBranch = currentBranch;
    },

    Repository: function() {
        this.bodies = {};
        this.revisions = {};
        this.children = {};
    }
};

Dvcs.Mergers.Defaults["text"] = Dvcs.Mergers.simpleTextualMerger;

Dvcs.Checkout.prototype.setDirty = function(uuid) {
    this.dirty[uuid] = uuid;
    this.anyDirty = true;
}

Dvcs.Checkout.prototype.createFile = function() {
    var uuid = Dvcs.Util.random_uuid();
    if (Dvcs._debugMode) { uuid = "inode-" + uuid; }
    this.inodes[uuid] = {};
    this.setDirty(uuid);
    return uuid;
};

Dvcs.Checkout.prototype.deleteFile = function(uuid) {
    if (!this.inodes[uuid]) return false;
    delete this.inodes[uuid];
    this.anyDirty = true;
    return true;
};

Dvcs.Checkout.prototype.fileExists = function(uuid) {
    return !!(this.inodes[uuid]);
};

Dvcs.Checkout.prototype.hasProp = function(uuid, prop) {
    var inode = this.inodes[uuid];
    if (!inode) return null;
    return (inode[prop] !== undefined);
}

Dvcs.Checkout.prototype.getProp = function(uuid, prop, defaultValue) {
    var inode = this.inodes[uuid];
    if (!inode) return null;
    var v = inode[prop];
    if (v === undefined) {
	return defaultValue;
    } else {
	return Dvcs.Util.deepCopy(v);
    }
};

Dvcs.Checkout.prototype.setProp = function(uuid, prop, value) {
    var inode = this.inodes[uuid];
    if (!inode) return false;
    inode[prop] = value;
    this.setDirty(uuid);
    return true;
};

Dvcs.Checkout.prototype.clearProp = function(uuid, prop) {
    var inode = this.inodes[uuid];
    if (!inode) return null;
    if (inode[prop] !== undefined) {
	delete inode[prop];
	this.setDirty(uuid);
    }
    return true;
}

Dvcs.Checkout.prototype.forEachProp = function(uuid, f) {
    var inode = this.inodes[uuid];
    if (!inode) return null;
    for (var prop in inode) {
	f(prop, inode[prop]);
    }
}

Dvcs.Checkout.prototype.forEachFile = function(f) {
    for (var uuid in this.inodes) {
	f(uuid);
    }
};

Dvcs.Checkout.prototype.getBranch = function() {
    return this.currentBranch;
};

Dvcs.Checkout.prototype.setBranch = function(newBranch) {
    this.currentBranch = newBranch;
};

Dvcs.Checkout.prototype.clone = function() {
    var result = new Dvcs.Checkout(this.directParent,
                                   this.additionalParent,
                                   this.currentBranch);
    result.inodes = Dvcs.Util.deepCopy(this.inodes);
    return result;
};

Dvcs.Repository.prototype.resolveRevId = function(revId) {
    if (this.revisions[revId]) {
        return revId;
    } else {
        return this.branchTip(revId);
    }
};

Dvcs.Repository.prototype.lookupRev = function(revId, shouldResolve) {
    var candidate = this.revisions[revId];
    if (!candidate && (shouldResolve !== false)) {
        // shouldResolve is an optional parameter, hence the odd test in the line above
        candidate = this.revisions[this.branchTip(revId)];
    }
    return candidate
        || { alive: {},
             dead: {},
             changed: [],
             branch: null,
             timestamp: 0,
             metadata: null, 
             directParent: null,
             additionalParent: null };
};

Dvcs.Repository.prototype.getMetadata = function(revId, shouldResolve) {
    return this.lookupRev(revId, shouldResolve).metadata;
};

Dvcs.Repository.prototype.getBody = function(revRecord, aliveInodeId) {
    var bodyId = revRecord.alive[aliveInodeId];
    if (!bodyId) return {};
    return Dvcs.Util.deepCopy(this.bodies[bodyId]);
};

Dvcs.Repository.prototype.update = function(unresolvedRevId) {
    var revId = this.resolveRevId(unresolvedRevId);
    var rev = this.revisions[revId];
    if (!rev) {
        if (unresolvedRevId === null) {
            // meaning "default branch". We only get here if the user
            // asked for the default branch and there are currently no
            // commits at all in the repo. Hand back an empty
            // checkout.
            return new Dvcs.Checkout(null, null, null);
        } else {
            // Couldn't find what the user asked for.
            return null;
        }
    }

    var fs = new Dvcs.Checkout(revId, null, rev.branch);
    for (var inode in rev.alive) {
        fs.inodes[inode] = this.getBody(rev, inode);
    }
    return fs;
};

Dvcs.Repository.prototype.commit = function(fs, metadata) {
    if (!fs.anyDirty) {
	return null;
    }

    var directParentRev = this.lookupRev(fs.directParent);
    var additionalParentRev = this.lookupRev(fs.additionalParent);

    var oldAlive = Dvcs.Util.dict_union(directParentRev.alive, additionalParentRev.alive);
    var oldDead = Dvcs.Util.dict_union(directParentRev.dead, additionalParentRev.dead);

    var newChanged = [];
    var newAlive = {};
    for (var inodeId in fs.inodes) {
        if (fs.dirty[inodeId]) {
            var newBodyId = Dvcs.Util.random_uuid();
            if (Dvcs._debugMode) { newBodyId = "body-" + newBodyId; }
            this.bodies[newBodyId] = Dvcs.Util.deepCopy(fs.inodes[inodeId]);
            newAlive[inodeId] = newBodyId;
            newChanged.push(inodeId);
        } else {
            newAlive[inodeId] = oldAlive[inodeId];
        }
    }

    var newDead = Dvcs.Util.dict_to_set(Dvcs.Util.dict_union(oldDead,
                                                             Dvcs.Util.dict_difference(oldAlive,
                                                                                       newAlive)));

    var rev = { alive: newAlive,
                dead: newDead,
                changed: newChanged,
                branch: fs.getBranch(),
                timestamp: (new Date()).getTime(),
                metadata: metadata,
                directParent: fs.directParent,
                additionalParent: fs.additionalParent };

    var newRevId = Dvcs.Util.random_uuid();
    if (Dvcs._debugMode) { newRevId = "rev-" + newRevId; }
    this.recordRevision(newRevId, rev);

    fs.directParent = newRevId;
    fs.additionalParent = null;
    fs.dirty = {};
    fs.anyDirty = false;

    return newRevId;
};

Dvcs.Repository.prototype.lookupParents = function (revId) {
    var r = this.lookupRev(revId);
    var result = [];
    if (r.directParent) result.push(r.directParent);
    if (r.additionalParent) result.push(r.additionalParent);
    return result;
};

Dvcs.Repository.prototype.lookupChildren = function (revId) {
    return this.children[revId] || [];
};

Dvcs.Repository.prototype.canMerge = function(r1, r2) {
    var $elf = this;
    function lookupParents(revId) { return $elf.lookupParents(revId); }
    var ancestorRevId = Graph.least_common_ancestor(lookupParents, r1, r2);
    return !(r1 == ancestorRevId || r2 == ancestorRevId);
}

Dvcs.Repository.prototype.merge = function(r1, r2) {
    var rev1 = this.lookupRev(r1);
    var rev2 = this.lookupRev(r2);

    var $elf = this;
    function lookupParents(revId) { return $elf.lookupParents(revId); }

    var ancestorRevId = Graph.least_common_ancestor(lookupParents, r1, r2);
    var ancestorRev = this.lookupRev(ancestorRevId, false);

    if (r1 == ancestorRevId || r2 == ancestorRevId) {
	return null;
    }

    var fs = this.update(r1);
    fs.additionalParent = r2;
    fs.anyDirty = true;

    var conflicts = [];

    for (var deadInode in rev2.dead) {
        fs.deleteFile(deadInode);
    }
    for (var aliveInode in rev2.alive) {
        if (fs.fileExists(aliveInode)) {
            if (ancestorRev.alive[aliveInode] != rev1.alive[aliveInode] ||
                ancestorRev.alive[aliveInode] != rev2.alive[aliveInode])
            {
                // It has a different body from the ancestor in one or
                // both of the revs being merged.
                var body0 = this.getBody(ancestorRev, aliveInode);
                var body1 = fs.inodes[aliveInode];
                var body2 = this.getBody(rev2, aliveInode);
                this.mergeBodies(body1, body0, body2,
                                 function (mergedBody) {
                                     fs.inodes[aliveInode] = mergedBody;
				     fs.setDirty(aliveInode);
                                 },
                                 function (partialResult, conflictDetails) {
                                     conflicts.push({inode: aliveInode,
                                                     partialResult: partialResult,
                                                     conflictDetails: conflictDetails});
                                 });
            } else {
                // It is unchanged. Leave it alone.
            }
        } else if (!rev1.dead[aliveInode]) {
            fs.inodes[aliveInode] = this.getBody(rev2, aliveInode);
	    fs.setDirty(aliveInode);
        }
    }

    return {files: fs, conflicts: conflicts, ancestor: ancestorRevId};
};

Dvcs.Repository.prototype.lookupMerger = function(prop) {
    return Dvcs.Mergers.Defaults[prop] || Dvcs.Mergers.simpleScalarMerger;
};

Dvcs.Repository.prototype.mergeBodies = function(bThis, bBase, bOther, kSuccess, kConflict) {
    var props = Dvcs.Util.dict_union(bThis, bOther);
    var bResult = {};
    var failures = {};
    var haveConflicts = false;
    for (var prop in props) {
        var merger = this.lookupMerger(prop);
        var mergedPropValue = merger(bThis[prop], bBase[prop], bOther[prop]);
        if (mergedPropValue.length == 1 && mergedPropValue[0].ok) {
            bResult[prop] = mergedPropValue[0].ok;
        } else {
            failures[prop] = mergedPropValue;
            haveConflicts = true;
        }
    }

    if (haveConflicts) {
        return kConflict(bResult, failures);
    } else {
        return kSuccess(bResult);
    }
};

Dvcs.Repository.prototype.recordRevision = function(newRevId, rev) {
    var $elf = this;
    function addChild(parentId) {
        if (parentId === null) return;
        if (!$elf.children[parentId]) {
            $elf.children[parentId] = [newRevId];
        } else {
            $elf.children[parentId].push(newRevId);
        }
    }
    this.revisions[newRevId] = rev;
    addChild(rev.directParent);
    addChild(rev.additionalParent);
};

Dvcs.Repository.prototype.exportRevisions = function(revIds) {
    if (revIds) {
        var revs = {};
        for (var i = 0; i < revIds; i++) {
            var rev = this.revisions[revIds[i]];
            if (rev) revs[revIds[i]] = rev;
        }

        var bodies = {};
        for (var revId in revs) {
            var alive = revs[revId].alive;
            for (var inodeId in alive) {
                var bodyId = alive[inodeId];
                bodies[bodyId] = this.bodies[bodyId];
            }
        }

        return {revisions: revs, bodies: bodies};
    } else {
        // Shortcut for all revisions. Be warned: shares structure!
        return {revisions: this.revisions, bodies: this.bodies};
    }
};

Dvcs.Repository.prototype.importRevisions = function(e) {
    var stats = {
	bodyCount: 0,
	bodyDups: 0,
	revCount: 0,
	revDups: 0
    };
    for (var bodyId in e.bodies) {
	if (!this.bodies[bodyId]) {
            this.bodies[bodyId] = e.bodies[bodyId];
	    stats.bodyCount++;
	} else {
	    stats.bodyDups++;
	}
    }
    for (var revId in e.revisions) {
	if (!this.revisions[revId]) {
            this.recordRevision(revId, e.revisions[revId]);
	    stats.revCount++;
	} else {
	    stats.revDups++;
	}
    }
    return stats;
};

Dvcs.Repository.prototype.allRevisions = function() {
    return Dvcs.Util.dict_to_set(this.revisions);
};

Dvcs.Repository.prototype.branchHeads = function(branch) {
    var result = [];
    for (var revId in this.revisions) {
        var rev = this.revisions[revId];
        if (rev.branch == branch) {
            var hasChildrenWithinBranch = false;
            var kids = this.children[revId] || [];
            for (var i = 0; i < kids.length; i++) {
                if (this.revisions[kids[i]].branch == branch) {
                    hasChildrenWithinBranch = true;
                    break;
                }
            }
            if (!hasChildrenWithinBranch) {
                result.push(revId);
            }
        }
    }
    return result;
};

Dvcs.Repository.prototype.branchTip = function(branch) {
    var newestHead = null;
    var newestRev = null;
    var branchHeads = this.branchHeads(branch);
    for (var i = 0; i < branchHeads.length; i++) {
        var id = branchHeads[i];
        var rev = this.lookupRev(id);
        if (newestHead === null || newestRev.timestamp < rev.timestamp) {
            newestHead = id;
            newestRev = rev;
        }
    }
    return newestHead;
};

Dvcs.Repository.prototype.allBranches = function() {
    var branches = {};
    for (var revId in this.revisions) {
        var rev = this.revisions[revId];
        var branch = rev.branch;
        var branchRecord = branches[branch];
        if (!branchRecord) {
            branchRecord = { active: false, heads: [] };
            branches[branch] = branchRecord;
        }

        var hasChildrenWithinBranch = false;
        var kids = this.children[revId] || [];
        for (var i = 0; i < kids.length; i++) {
            if (this.revisions[kids[i]].branch == branch) {
                hasChildrenWithinBranch = true;
                break;
            }
        }
        if (!hasChildrenWithinBranch) {
            branchRecord.heads.push(revId);
            if (kids.length === 0) {
                branchRecord.active = true;
            }
        }
    }
    return branches;
};

Dvcs.Repository.prototype.childlessRevisions = function() {
    var result = [];
    for (var revId in this.revisions) {
        var kids = this.children[revId] || [];
        if (kids.length === 0) {
            result.push(revId);
        }
    }
    var revs = this.revisions;
    result.sort(function (r1, r2) { return revs[r2].timestamp - revs[r1].timestamp; });
    return result;
};

Dvcs.Repository.prototype.fileRevisions = function(uuid) {
    var result = {};
    for (var revId in this.revisions) {
        var rev = this.revisions[revId];
        for (var i = rev.changed.length - 1; i >= 0; i--) {
            if (uuid == rev.changed[i]) {
                result[revId] = rev;
                break;
            }
        }
    }
    return result;
};