1// Copyright (c) 2013 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5'use strict'; 6 7/** 8 * @fileoverview Provides the TimeToObjectInstanceMap class. 9 */ 10base.require('base.range'); 11base.require('base.sorted_array_utils'); 12 13base.exportTo('tracing.trace_model', function() { 14 15 /** 16 * Tracks all the instances associated with a given ID over its lifetime. 17 * 18 * An id can be used multiple times throughout a trace, referring to different 19 * objects at different times. This data structure does the bookkeeping to 20 * figure out what ObjectInstance is referred to at a given timestamp. 21 * 22 * @constructor 23 */ 24 function TimeToObjectInstanceMap(createObjectInstanceFunction, parent, id) { 25 this.createObjectInstanceFunction_ = createObjectInstanceFunction; 26 this.parent = parent; 27 this.id = id; 28 this.instances = []; 29 } 30 31 TimeToObjectInstanceMap.prototype = { 32 idWasCreated: function(category, name, ts) { 33 if (this.instances.length == 0) { 34 this.instances.push(this.createObjectInstanceFunction_( 35 this.parent, this.id, category, name, ts)); 36 this.instances[0].creationTsWasExplicit = true; 37 return this.instances[0]; 38 } 39 40 var lastInstance = this.instances[this.instances.length - 1]; 41 if (ts < lastInstance.deletionTs) { 42 throw new Error('Mutation of the TimeToObjectInstanceMap must be ' + 43 'done in ascending timestamp order.'); 44 } 45 lastInstance = this.createObjectInstanceFunction_( 46 this.parent, this.id, category, name, ts); 47 lastInstance.creationTsWasExplicit = true; 48 this.instances.push(lastInstance); 49 return lastInstance; 50 }, 51 52 addSnapshot: function(category, name, ts, args) { 53 if (this.instances.length == 0) { 54 this.instances.push(this.createObjectInstanceFunction_( 55 this.parent, this.id, category, name, ts)); 56 } 57 58 var i = base.findLowIndexInSortedIntervals( 59 this.instances, 60 function(inst) { return inst.creationTs; }, 61 function(inst) { return inst.deletionTs - inst.creationTs; }, 62 ts); 63 64 var instance; 65 if (i < 0) { 66 instance = this.instances[0]; 67 if (ts > instance.deletionTs || 68 instance.creationTsWasExplicit) { 69 throw new Error( 70 'At the provided timestamp, no instance was still alive'); 71 } 72 73 if (instance.snapshots.length != 0) { 74 throw new Error( 75 'Cannot shift creationTs forward, ' + 76 'snapshots have been added. First snap was at ts=' + 77 instance.snapshots[0].ts + ' and creationTs was ' + 78 instance.creationTs); 79 } 80 instance.creationTs = ts; 81 } else if (i >= this.instances.length) { 82 instance = this.instances[this.instances.length - 1]; 83 if (ts >= instance.deletionTs) { 84 // The snap is added after our oldest and deleted instance. This means 85 // that this is a new implicit instance. 86 instance = this.createObjectInstanceFunction_( 87 this.parent, this.id, category, name, ts); 88 this.instances.push(instance); 89 } else { 90 // If the ts is before the last objects deletion time, then the caller 91 // is trying to add a snapshot when there may have been an instance 92 // alive. In that case, try to move an instance's creationTs to 93 // include this ts, provided that it has an implicit creationTs. 94 95 // Search backward from the right for an instance that was definitely 96 // deleted before this ts. Any time an instance is found that has a 97 // moveable creationTs 98 var lastValidIndex; 99 for (var i = this.instances.length - 1; i >= 0; i--) { 100 var tmp = this.instances[i]; 101 if (ts >= tmp.deletionTs) 102 break; 103 if (tmp.creationTsWasExplicit == false && tmp.snapshots.length == 0) 104 lastValidIndex = i; 105 } 106 if (lastValidIndex === undefined) { 107 throw new Error( 108 'Cannot add snapshot. No instance was alive that was mutable.'); 109 } 110 instance = this.instances[lastValidIndex]; 111 instance.creationTs = ts; 112 } 113 } else { 114 instance = this.instances[i]; 115 } 116 117 return instance.addSnapshot(ts, args); 118 }, 119 120 get lastInstance() { 121 if (this.instances.length == 0) 122 return undefined; 123 return this.instances[this.instances.length - 1]; 124 }, 125 126 idWasDeleted: function(category, name, ts) { 127 if (this.instances.length == 0) { 128 this.instances.push(this.createObjectInstanceFunction_( 129 this.parent, this.id, category, name, ts)); 130 } 131 var lastInstance = this.instances[this.instances.length - 1]; 132 if (ts < lastInstance.creationTs) 133 throw new Error('Cannot delete a id before it was crated'); 134 if (lastInstance.deletionTs == Number.MAX_VALUE) { 135 lastInstance.wasDeleted(ts); 136 return lastInstance; 137 } 138 139 if (ts < lastInstance.deletionTs) 140 throw new Error('id was already deleted earlier.'); 141 142 // A new instance was deleted with no snapshots in-between. 143 // Create an instance then kill it. 144 lastInstance = this.createObjectInstanceFunction_( 145 this.parent, this.id, category, name, ts); 146 this.instances.push(lastInstance); 147 return lastInstance; 148 }, 149 150 getInstanceAt: function(ts) { 151 var i = base.findLowIndexInSortedIntervals( 152 this.instances, 153 function(inst) { return inst.creationTs; }, 154 function(inst) { return inst.deletionTs - inst.creationTs; }, 155 ts); 156 if (i < 0) { 157 if (this.instances[0].creationTsWasExplicit) 158 return undefined; 159 return this.instances[0]; 160 } else if (i >= this.instances.length) { 161 return undefined; 162 } 163 return this.instances[i]; 164 } 165 }; 166 167 return { 168 TimeToObjectInstanceMap: TimeToObjectInstanceMap 169 }; 170}); 171