src/applications/differential/parser/DifferentialLineAdjustmentMap.php

   1 <?php
   2
   3 /**
   4  * Datastructure which follows lines of code across source changes.
   5  *
   6  * This map is used to update the positions of inline comments after diff
   7  * updates. For example, if a inline comment appeared on line 30 of a diff
   8  * but the next update adds 15 more lines above it, the comment should move
   9  * down to line 45.
  10  *
  11  */
  12 final class DifferentialLineAdjustmentMap extends Phobject {
  13
  14   private $map;
  15   private $nearestMap;
  16   private $isInverse;
  17   private $finalOffset;
  18   private $nextMapInChain;
  19
  20   /**
  21    * Get the raw adjustment map.
  22    */
  23   public function getMap() {
  24     return $this->map;
  25   }
  26
  27   public function getNearestMap() {
  28     if ($this->nearestMap === null) {
  29       $this->buildNearestMap();
  30     }
  31
  32     return $this->nearestMap;
  33   }
  34
  35   public function getFinalOffset() {
  36     // Make sure we've built this map already.
  37     $this->getNearestMap();
  38     return $this->finalOffset;
  39   }
  40
  41
  42   /**
  43    * Add a map to the end of the chain.
  44    *
  45    * When a line is mapped with @{method:mapLine}, it is mapped through all
  46    * maps in the chain.
  47    */
  48   public function addMapToChain(DifferentialLineAdjustmentMap $map) {
  49     if ($this->nextMapInChain) {
  50       $this->nextMapInChain->addMapToChain($map);
  51     } else {
  52       $this->nextMapInChain = $map;
  53     }
  54     return $this;
  55   }
  56
  57
  58   /**
  59    * Map a line across a change, or a series of changes.
  60    *
  61    * @param int Line to map
  62    * @param bool True to map it as the end of a range.
  63    * @return wild Spooky magic.
  64    */
  65   public function mapLine($line, $is_end) {
  66     $nmap = $this->getNearestMap();
  67
  68     $deleted = false;
  69     $offset = false;
  70     if (isset($nmap[$line])) {
  71       $line_range = $nmap[$line];
  72       if ($is_end) {
  73         $to_line = end($line_range);
  74       } else {
  75         $to_line = reset($line_range);
  76       }
  77       if ($to_line <= 0) {
  78         // If we're tracing the first line and this block is collapsing,
  79         // compute the offset from the top of the block.
  80         if (!$is_end && $this->isInverse) {
  81           $offset = 1;
  82           $cursor = $line - 1;
  83           while (isset($nmap[$cursor])) {
  84             $prev = $nmap[$cursor];
  85             $prev = reset($prev);
  86             if ($prev == $to_line) {
  87               $offset++;
  88             } else {
  89               break;
  90             }
  91             $cursor--;
  92           }
  93         }
  94
  95         $to_line = -$to_line;
  96         if (!$this->isInverse) {
  97           $deleted = true;
  98         }
  99       }
 100       $line = $to_line;
 101     } else {
 102       $line = $line + $this->finalOffset;
 103     }
 104
 105     if ($this->nextMapInChain) {
 106       $chain = $this->nextMapInChain->mapLine($line, $is_end);
 107       list($chain_deleted, $chain_offset, $line) = $chain;
 108       $deleted = ($deleted || $chain_deleted);
 109       if ($chain_offset !== false) {
 110         if ($offset === false) {
 111           $offset = 0;
 112         }
 113         $offset += $chain_offset;
 114       }
 115     }
 116
 117     return array($deleted, $offset, $line);
 118   }
 119
 120
 121   /**
 122    * Build a derived map which maps deleted lines to the nearest valid line.
 123    *
 124    * This computes a "nearest line" map and a final-line offset. These
 125    * derived maps allow us to map deleted code to the previous (or next) line
 126    * which actually exists.
 127    */
 128   private function buildNearestMap() {
 129     $map = $this->map;
 130     $nmap = array();
 131
 132     $nearest = 0;
 133     foreach ($map as $key => $value) {
 134       if ($value) {
 135         $nmap[$key] = $value;
 136         $nearest = end($value);
 137       } else {
 138         $nmap[$key][0] = -$nearest;
 139       }
 140     }
 141
 142     if (isset($key)) {
 143       $this->finalOffset = ($nearest - $key);
 144     } else {
 145       $this->finalOffset = 0;
 146     }
 147
 148     foreach (array_reverse($map, true) as $key => $value) {
 149       if ($value) {
 150         $nearest = reset($value);
 151       } else {
 152         $nmap[$key][1] = -$nearest;
 153       }
 154     }
 155
 156     $this->nearestMap = $nmap;
 157
 158     return $this;
 159   }
 160
 161   public static function newFromHunks(array $hunks) {
 162     assert_instances_of($hunks, 'DifferentialHunk');
 163
 164     $map = array();
 165     $o = 0;
 166     $n = 0;
 167
 168     $hunks = msort($hunks, 'getOldOffset');
 169     foreach ($hunks as $hunk) {
 170
 171       // If the hunks are disjoint, add the implied missing lines where
 172       // nothing changed.
 173       $min = ($hunk->getOldOffset() - 1);
 174       while ($o < $min) {
 175         $o++;
 176         $n++;
 177         $map[$o][] = $n;
 178       }
 179
 180       $lines = $hunk->getStructuredLines();
 181       foreach ($lines as $line) {
 182         switch ($line['type']) {
 183           case '-':
 184             $o++;
 185             $map[$o] = array();
 186             break;
 187           case '+':
 188             $n++;
 189             $map[$o][] = $n;
 190             break;
 191           case ' ':
 192             $o++;
 193             $n++;
 194             $map[$o][] = $n;
 195             break;
 196           default:
 197             break;
 198         }
 199       }
 200     }
 201
 202     $map = self::reduceMapRanges($map);
 203
 204     return self::newFromMap($map);
 205   }
 206
 207   public static function newFromMap(array $map) {
 208     $obj = new DifferentialLineAdjustmentMap();
 209     $obj->map = $map;
 210     return $obj;
 211   }
 212
 213   public static function newInverseMap(DifferentialLineAdjustmentMap $map) {
 214     $old = $map->getMap();
 215     $inv = array();
 216     $last = 0;
 217     foreach ($old as $k => $v) {
 218       if (count($v) > 1) {
 219         $v = range(reset($v), end($v));
 220       }
 221       if ($k == 0) {
 222         foreach ($v as $line) {
 223           $inv[$line] = array();
 224           $last = $line;
 225         }
 226       } else if ($v) {
 227         $first = true;
 228         foreach ($v as $line) {
 229           if ($first) {
 230             $first = false;
 231             $inv[$line][] = $k;
 232             $last = $line;
 233           } else {
 234             $inv[$line] = array();
 235           }
 236         }
 237       } else {
 238         $inv[$last][] = $k;
 239       }
 240     }
 241
 242     $inv = self::reduceMapRanges($inv);
 243
 244     $obj = new DifferentialLineAdjustmentMap();
 245     $obj->map = $inv;
 246     $obj->isInverse = !$map->isInverse;
 247     return $obj;
 248   }
 249
 250   private static function reduceMapRanges(array $map) {
 251     foreach ($map as $key => $values) {
 252       if (count($values) > 2) {
 253         $map[$key] = array(reset($values), end($values));
 254       }
 255     }
 256     return $map;
 257   }
 258
 259
 260   public static function loadMaps(array $maps) {
 261     $keys = array();
 262     foreach ($maps as $map) {
 263       list($u, $v) = $map;
 264       $keys[self::getCacheKey($u, $v)] = $map;
 265     }
 266
 267     $cache = new PhabricatorKeyValueDatabaseCache();
 268     $cache = new PhutilKeyValueCacheProfiler($cache);
 269     $cache->setProfiler(PhutilServiceProfiler::getInstance());
 270
 271     $results = array();
 272
 273     if ($keys) {
 274       $caches = $cache->getKeys(array_keys($keys));
 275       foreach ($caches as $key => $value) {
 276         list($u, $v) = $keys[$key];
 277         try {
 278           $results[$u][$v] = self::newFromMap(
 279             phutil_json_decode($value));
 280         } catch (Exception $ex) {
 281           // Ignore, rebuild below.
 282         }
 283         unset($keys[$key]);
 284       }
 285     }
 286
 287     if ($keys) {
 288       $built = self::buildMaps($maps);
 289
 290       $write = array();
 291       foreach ($built as $u => $list) {
 292         foreach ($list as $v => $map) {
 293           $write[self::getCacheKey($u, $v)] = json_encode($map->getMap());
 294           $results[$u][$v] = $map;
 295         }
 296       }
 297
 298       $cache->setKeys($write);
 299     }
 300
 301     return $results;
 302   }
 303
 304   private static function buildMaps(array $maps) {
 305     $need = array();
 306     foreach ($maps as $map) {
 307       list($u, $v) = $map;
 308       $need[$u] = $u;
 309       $need[$v] = $v;
 310     }
 311
 312     if ($need) {
 313       $changesets = id(new DifferentialChangesetQuery())
 314         ->setViewer(PhabricatorUser::getOmnipotentUser())
 315         ->withIDs($need)
 316         ->needHunks(true)
 317         ->execute();
 318       $changesets = mpull($changesets, null, 'getID');
 319     }
 320
 321     $results = array();
 322     foreach ($maps as $map) {
 323       list($u, $v) = $map;
 324       $u_set = idx($changesets, $u);
 325       $v_set = idx($changesets, $v);
 326
 327       if (!$u_set || !$v_set) {
 328         continue;
 329       }
 330
 331       // This is the simple case.
 332       if ($u == $v) {
 333         $results[$u][$v] = self::newFromHunks(
 334           $u_set->getHunks());
 335         continue;
 336       }
 337
 338       $u_old = $u_set->makeOldFile();
 339       $v_old = $v_set->makeOldFile();
 340
 341       // No difference between the two left sides.
 342       if ($u_old == $v_old) {
 343         $results[$u][$v] = self::newFromMap(
 344           array());
 345         continue;
 346       }
 347
 348       // If we're missing context, this won't currently work. We can
 349       // make this case work, but it's fairly rare.
 350       $u_hunks = $u_set->getHunks();
 351       $v_hunks = $v_set->getHunks();
 352       if (count($u_hunks) != 1 ||
 353           count($v_hunks) != 1 ||
 354           head($u_hunks)->getOldOffset() != 1 ||
 355           head($u_hunks)->getNewOffset() != 1 ||
 356           head($v_hunks)->getOldOffset() != 1 ||
 357           head($v_hunks)->getNewOffset() != 1) {
 358         continue;
 359       }
 360
 361       $changeset = id(new PhabricatorDifferenceEngine())
 362         ->generateChangesetFromFileContent($u_old, $v_old);
 363
 364       $results[$u][$v] = self::newFromHunks(
 365         $changeset->getHunks());
 366     }
 367
 368     return $results;
 369   }
 370
 371   private static function getCacheKey($u, $v) {
 372     return 'diffadjust.v1('.$u.','.$v.')';
 373   }
 374
 375 }