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