Page MenuHomestyx hydra
Files F271648

No OneTemporary
Actions

View Options

diff --git a/src/applications/phrequent/storage/PhrequentTimeBlock.php b/src/applications/phrequent/storage/PhrequentTimeBlock.php
index 866275ac08..60721e45ca 100644
--- a/src/applications/phrequent/storage/PhrequentTimeBlock.php
+++ b/src/applications/phrequent/storage/PhrequentTimeBlock.php
@@ -1,155 +1,268 @@
<?php
final class PhrequentTimeBlock extends Phobject {
private $events;
public function __construct(array $events) {
assert_instances_of($events, 'PhrequentUserTime');
$this->events = $events;
}
public function getTimeSpentOnObject($phid, $now) {
$ranges = idx($this->getObjectTimeRanges($now), $phid, array());
$sum = 0;
foreach ($ranges as $range) {
$sum += ($range[1] - $range[0]);
}
return $sum;
}
public function getObjectTimeRanges($now) {
$ranges = array();
$object_ranges = array();
foreach ($this->events as $event) {
// First, convert each event's preempting stack into a linear timeline
// of events.
$timeline = array();
$timeline[] = array(
+ 'event' => $event,
'at' => $event->getDateStarted(),
'type' => 'start',
);
$timeline[] = array(
+ 'event' => $event,
'at' => nonempty($event->getDateEnded(), $now),
'type' => 'end',
);
$base_phid = $event->getObjectPHID();
$preempts = $event->getPreemptingEvents();
foreach ($preempts as $preempt) {
$same_object = ($preempt->getObjectPHID() == $base_phid);
$timeline[] = array(
+ 'event' => $preempt,
'at' => $preempt->getDateStarted(),
'type' => $same_object ? 'start' : 'push',
);
$timeline[] = array(
+ 'event' => $preempt,
'at' => nonempty($preempt->getDateEnded(), $now),
'type' => $same_object ? 'end' : 'pop',
);
}
// Now, figure out how much time was actually spent working on the
// object.
- $timeline = isort($timeline, 'at');
+ usort($timeline, array(__CLASS__, 'sortTimeline'));
$stack = array();
$depth = null;
+ // NOTE: "Strata" track the separate layers between each event tracking
+ // the object we care about. Events might look like this:
+ //
+ // |xxxxxxxxxxxxxxxxx|
+ // |yyyyyyy|
+ // |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
+ // 9AM 5PM
+ //
+ // ...where we care about event "x". When "y" is popped, that shouldn't
+ // pop the top stack -- we need to pop the stack a level down. Each
+ // event tracking "x" creates a new stratum, and we keep track of where
+ // timeline events are among the strata in order to keep stack depths
+ // straight.
+
+ $stratum = null;
+ $strata = array();
+
+
$ranges = array();
foreach ($timeline as $timeline_event) {
- switch ($timeline_event['type']) {
+ $id = $timeline_event['event']->getID();
+ $type = $timeline_event['type'];
+
+ switch ($type) {
case 'start':
$stack[] = $depth;
$depth = 0;
+ $stratum = count($stack);
+ $strata[$id] = $stratum;
$range_start = $timeline_event['at'];
break;
case 'end':
- if ($depth == 0) {
- $ranges[] = array($range_start, $timeline_event['at']);
+ if ($strata[$id] == $stratum) {
+ if ($depth == 0) {
+ $ranges[] = array($range_start, $timeline_event['at']);
+ $depth = array_pop($stack);
+ } else {
+ // Here, we've prematurely ended the current stratum. Merge all
+ // the higher strata into it. This looks like this:
+ //
+ // V
+ // V
+ // |zzzzzzzz|
+ // |xxxxx|
+ // |yyyyyyyyyyyyy|
+ // |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
+
+ $depth = array_pop($stack) + $depth;
+ }
+ } else {
+ // Here, we've prematurely ended a deeper stratum. Merge higher
+ // stata. This looks like this:
+ //
+ // V
+ // V
+ // |aaaaaaa|
+ // |xxxxxxxxxxxxxxxxxxx|
+ // |zzzzzzzzzzzzz|
+ // |xxxxxxx|
+ // |yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy|
+ // |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
+
+ $extra = $stack[$strata[$id]];
+ unset($stack[$strata[$id] - 1]);
+ $stack = array_values($stack);
+ $stack[$strata[$id] - 1] += $extra;
+ }
+
+ // Regardless of how we got here, we need to merge down any higher
+ // strata.
+ $target = $strata[$id];
+ foreach ($strata as $strata_id => $id_stratum) {
+ if ($id_stratum >= $target) {
+ $strata[$strata_id]--;
+ }
}
- $depth = array_pop($stack);
+ $stratum = count($stack);
+
+ unset($strata[$id]);
break;
case 'push':
+ $strata[$id] = $stratum;
if ($depth == 0) {
$ranges[] = array($range_start, $timeline_event['at']);
}
$depth++;
break;
case 'pop':
- $depth--;
- if ($depth == 0) {
- $range_start = $timeline_event['at'];
+ if ($strata[$id] == $stratum) {
+ $depth--;
+ if ($depth == 0) {
+ $range_start = $timeline_event['at'];
+ }
+ } else {
+ $stack[$strata[$id]]--;
}
+ unset($strata[$id]);
break;
}
}
$object_ranges[$base_phid][] = $ranges;
}
// Finally, collapse all the ranges so we don't double-count time.
foreach ($object_ranges as $phid => $ranges) {
$object_ranges[$phid] = self::mergeTimeRanges(array_mergev($ranges));
}
return $object_ranges;
}
/**
* Merge a list of time ranges (pairs of `<start, end>` epochs) so that no
* elements overlap. For example, the ranges:
*
* array(
* array(50, 150),
* array(100, 175),
* );
*
* ...are merged to:
*
* array(
* array(50, 175),
* );
*
* This is used to avoid double-counting time on objects which had timers
* started multiple times.
*
* @param list<pair<int, int>> List of possibly overlapping time ranges.
* @return list<pair<int, int>> Nonoverlapping time ranges.
*/
public static function mergeTimeRanges(array $ranges) {
$ranges = isort($ranges, 0);
$result = array();
$current = null;
foreach ($ranges as $key => $range) {
if ($current === null) {
$current = $range;
continue;
}
if ($range[0] <= $current[1]) {
$current[1] = max($range[1], $current[1]);
continue;
}
$result[] = $current;
$current = $range;
}
$result[] = $current;
return $result;
}
+
+ /**
+ * Sort events in timeline order. Notably, for events which occur on the same
+ * second, we want to process end events after start events.
+ */
+ public static function sortTimeline(array $u, array $v) {
+ // If these events occur at different times, ordering is obvious.
+ if ($u['at'] != $v['at']) {
+ return ($u['at'] < $v['at']) ? -1 : 1;
+ }
+
+ $u_end = ($u['type'] == 'end' || $u['type'] == 'pop');
+ $v_end = ($v['type'] == 'end' || $v['type'] == 'pop');
+
+ $u_id = $u['event']->getID();
+ $v_id = $v['event']->getID();
+
+ if ($u_end == $v_end) {
+ // These are both start events or both end events. Sort them by ID.
+ if (!$u_end) {
+ return ($u_id < $v_id) ? -1 : 1;
+ } else {
+ return ($u_id < $v_id) ? 1 : -1;
+ }
+ } else {
+ // Sort them (start, end) if they're the same event, and (end, start)
+ // otherwise.
+ if ($u_id == $v_id) {
+ return $v_end ? -1 : 1;
+ } else {
+ return $v_end ? 1 : -1;
+ }
+ }
+
+ return 0;
+ }
+
}
diff --git a/src/applications/phrequent/storage/__tests__/PhrequentTimeBlockTestCase.php b/src/applications/phrequent/storage/__tests__/PhrequentTimeBlockTestCase.php
index 0c110c36d5..6bb09b5497 100644
--- a/src/applications/phrequent/storage/__tests__/PhrequentTimeBlockTestCase.php
+++ b/src/applications/phrequent/storage/__tests__/PhrequentTimeBlockTestCase.php
@@ -1,128 +1,226 @@
<?php
final class PhrequentTimeBlockTestCase extends PhabricatorTestCase {
public function testMergeTimeRanges() {
// Overlapping ranges.
$input = array(
array(50, 150),
array(100, 175),
);
$expect = array(
array(50, 175),
);
$this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input));
// Identical ranges.
$input = array(
array(1, 1),
array(1, 1),
array(1, 1),
);
$expect = array(
array(1, 1),
);
$this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input));
// Range which is a strict subset of another range.
$input = array(
array(2, 7),
array(1, 10),
);
$expect = array(
array(1, 10),
);
$this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input));
// These are discontinuous and should not be merged.
$input = array(
array(5, 6),
array(7, 8),
);
$expect = array(
array(5, 6),
array(7, 8),
);
$this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input));
// These overlap only on an edge, but should merge.
$input = array(
array(5, 6),
array(6, 7),
);
$expect = array(
array(5, 7),
);
$this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input));
}
public function testPreemptingEvents() {
// Roughly, this is: got into work, started T1, had a meeting from 10-11,
// left the office around 2 to meet a client at a coffee shop, worked on
// T1 again for about 40 minutes, had the meeting from 3-3:30, finished up
// on T1, headed back to the office, got another hour of work in, and
// headed home.
$event = $this->newEvent('T1', 900, 1700);
$event->attachPreemptingEvents(
array(
$this->newEvent('meeting', 1000, 1100),
$this->newEvent('offsite', 1400, 1600),
$this->newEvent('T1', 1420, 1580),
$this->newEvent('offsite meeting', 1500, 1550),
));
$block = new PhrequentTimeBlock(array($event));
$ranges = $block->getObjectTimeRanges(1800);
$this->assertEqual(
array(
'T1' => array(
array(900, 1000), // Before morning meeting.
array(1100, 1400), // After morning meeting.
array(1420, 1500), // Coffee, before client meeting.
array(1550, 1580), // Coffee, after client meeting.
array(1600, 1700), // After returning from off site.
),
),
$ranges);
-
$event = $this->newEvent('T2', 100, 300);
$event->attachPreemptingEvents(
array(
$this->newEvent('meeting', 200, null),
));
$block = new PhrequentTimeBlock(array($event));
$ranges = $block->getObjectTimeRanges(1000);
$this->assertEqual(
array(
'T2' => array(
array(100, 200),
),
),
$ranges);
}
+ public function testTimelineSort() {
+ $e1 = $this->newEvent('X1', 1, 1)->setID(1);
+
+ $in = array(
+ array(
+ 'event' => $e1,
+ 'at' => 1,
+ 'type' => 'start',
+ ),
+ array(
+ 'event' => $e1,
+ 'at' => 1,
+ 'type' => 'end',
+ ),
+ );
+
+ usort($in, array('PhrequentTimeBlock', 'sortTimeline'));
+
+ $this->assertEqual(
+ array(
+ 'start',
+ 'end',
+ ),
+ ipull($in, 'type'));
+ }
+
+ public function testInstantaneousEvent() {
+
+ $event = $this->newEvent('T1', 8, 8);
+ $event->attachPreemptingEvents(array());
+
+ $block = new PhrequentTimeBlock(array($event));
+
+ $ranges = $block->getObjectTimeRanges(1800);
+ $this->assertEqual(
+ array(
+ 'T1' => array(
+ array(8, 8),
+ ),
+ ),
+ $ranges);
+ }
+
+ public function testPopAcrossStrata() {
+
+ $event = $this->newEvent('T1', 1, 1000);
+ $event->attachPreemptingEvents(
+ array(
+ $this->newEvent('T2', 100, 300),
+ $this->newEvent('T1', 200, 400),
+ $this->newEvent('T3', 250, 275),
+ ));
+
+ $block = new PhrequentTimeBlock(array($event));
+
+ $ranges = $block->getObjectTimeRanges(1000);
+
+ $this->assertEqual(
+ array(
+ 'T1' => array(
+ array(1, 100),
+ array(200, 250),
+ array(275, 1000),
+ ),
+ ),
+ $ranges);
+ }
+
+ public function testEndDeeperStratum() {
+ $event = $this->newEvent('T1', 1, 1000);
+ $event->attachPreemptingEvents(
+ array(
+ $this->newEvent('T2', 100, 900),
+ $this->newEvent('T1', 200, 400),
+ $this->newEvent('T3', 300, 800),
+ $this->newEvent('T1', 350, 600),
+ $this->newEvent('T4', 380, 390),
+ ));
+
+ $block = new PhrequentTimeBlock(array($event));
+
+ $ranges = $block->getObjectTimeRanges(1000);
+
+ $this->assertEqual(
+ array(
+ 'T1' => array(
+ array(1, 100),
+ array(200, 300),
+ array(350, 380),
+ array(390, 600),
+ array(900, 1000),
+ ),
+ ),
+ $ranges);
+ }
+
private function newEvent($object_phid, $start_time, $end_time) {
+ static $id = 0;
+
return id(new PhrequentUserTime())
+ ->setID(++$id)
->setObjectPHID($object_phid)
->setDateStarted($start_time)
->setDateEnded($end_time);
}
}

File Metadata

Mime Type
text/x-diff
Expires
Thu, Aug 14, 5:48 AM (2 d, 13 h ago)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
202203
Default Alt Text
(14 KB)

Event Timeline

styx copyright 2020 sirocyl / ellie (kymkdd) / ncommander / styx contributors
Use of other names and brands is not intended to reflect a claim of, or right to, use the name or brand.
styx is an operating system using the Linux kernel and components, and "styx Linux" as a phrase does not reflect the inclusion of the Linux brand or trademark in the styx project.
Linux® is the registered trademark of Linus Torvalds in the U.S. and other countries.
Terms and Conditions (TODO: fix this!)