src/infrastructure/query/policy/PhabricatorCursorPagedPolicyAwareQuery.php

   1 <?php
   2
   3 /**
   4  * A query class which uses cursor-based paging. This paging is much more
   5  * performant than offset-based paging in the presence of policy filtering.
   6  *
   7  * @task cursors Query Cursors
   8  * @task clauses Building Query Clauses
   9  * @task appsearch Integration with ApplicationSearch
  10  * @task customfield Integration with CustomField
  11  * @task paging Paging
  12  * @task order Result Ordering
  13  * @task edgelogic Working with Edge Logic
  14  * @task spaces Working with Spaces
  15  */
  16 abstract class PhabricatorCursorPagedPolicyAwareQuery
  17   extends PhabricatorPolicyAwareQuery {
  18
  19   private $externalCursorString;
  20   private $internalCursorObject;
  21   private $isQueryOrderReversed = false;
  22   private $rawCursorRow;
  23
  24   private $applicationSearchConstraints = array();
  25   private $internalPaging;
  26   private $orderVector;
  27   private $groupVector;
  28   private $builtinOrder;
  29   private $edgeLogicConstraints = array();
  30   private $edgeLogicConstraintsAreValid = false;
  31   private $spacePHIDs;
  32   private $spaceIsArchived;
  33   private $ngrams = array();
  34   private $ferretEngine;
  35   private $ferretTokens = array();
  36   private $ferretTables = array();
  37   private $ferretQuery;
  38   private $ferretMetadata = array();
  39   private $ngramEngine;
  40
  41   const FULLTEXT_RANK = '_ft_rank';
  42   const FULLTEXT_MODIFIED = '_ft_epochModified';
  43   const FULLTEXT_CREATED = '_ft_epochCreated';
  44
  45 /* -(  Cursors  )------------------------------------------------------------ */
  46
  47   protected function newExternalCursorStringForResult($object) {
  48     if (!($object instanceof LiskDAO)) {
  49       throw new Exception(
  50         pht(
  51           'Expected to be passed a result object of class "LiskDAO" in '.
  52           '"newExternalCursorStringForResult()", actually passed "%s". '.
  53           'Return storage objects from "loadPage()" or override '.
  54           '"newExternalCursorStringForResult()".',
  55           phutil_describe_type($object)));
  56     }
  57
  58     return (string)$object->getID();
  59   }
  60
  61   protected function newInternalCursorFromExternalCursor($cursor) {
  62     $viewer = $this->getViewer();
  63
  64     $query = newv(get_class($this), array());
  65
  66     $query
  67       ->setParentQuery($this)
  68       ->setViewer($viewer);
  69
  70     // We're copying our order vector to the subquery so that the subquery
  71     // knows it should generate any supplemental information required by the
  72     // ordering.
  73
  74     // For example, Phriction documents may be ordered by title, but the title
  75     // isn't a column in the "document" table: the query must JOIN the
  76     // "content" table to perform the ordering. Passing the ordering to the
  77     // subquery tells it that we need it to do that JOIN and attach relevant
  78     // paging information to the internal cursor object.
  79
  80     // We only expect to load a single result, so the actual result order does
  81     // not matter. We only want the internal cursor for that result to look
  82     // like a cursor this parent query would generate.
  83     $query->setOrderVector($this->getOrderVector());
  84
  85     $this->applyExternalCursorConstraintsToQuery($query, $cursor);
  86
  87     // If we have a Ferret fulltext query, copy it to the subquery so that we
  88     // generate ranking columns appropriately, and compute the correct object
  89     // ranking score for the current query.
  90     if ($this->ferretEngine) {
  91       $query->withFerretConstraint($this->ferretEngine, $this->ferretTokens);
  92     }
  93
  94     // We're executing the subquery normally to make sure the viewer can
  95     // actually see the object, and that it's a completely valid object which
  96     // passes all filtering and policy checks. You aren't allowed to use an
  97     // object you can't see as a cursor, since this can leak information.
  98     $result = $query->executeOne();
  99     if (!$result) {
 100       $this->throwCursorException(
 101         pht(
 102           'Cursor "%s" does not identify a valid object in query "%s".',
 103           $cursor,
 104           get_class($this)));
 105     }
 106
 107     // Now that we made sure the viewer can actually see the object the
 108     // external cursor identifies, return the internal cursor the query
 109     // generated as a side effect while loading the object.
 110     return $query->getInternalCursorObject();
 111   }
 112
 113   final protected function throwCursorException($message) {
 114     throw new PhabricatorInvalidQueryCursorException($message);
 115   }
 116
 117   protected function applyExternalCursorConstraintsToQuery(
 118     PhabricatorCursorPagedPolicyAwareQuery $subquery,
 119     $cursor) {
 120     $subquery->withIDs(array($cursor));
 121   }
 122
 123   protected function newPagingMapFromCursorObject(
 124     PhabricatorQueryCursor $cursor,
 125     array $keys) {
 126
 127     $object = $cursor->getObject();
 128
 129     return $this->newPagingMapFromPartialObject($object);
 130   }
 131
 132   protected function newPagingMapFromPartialObject($object) {
 133     return array(
 134       'id' => (int)$object->getID(),
 135     );
 136   }
 137
 138   private function getExternalCursorStringForResult($object) {
 139     $cursor = $this->newExternalCursorStringForResult($object);
 140
 141     if (!is_string($cursor)) {
 142       throw new Exception(
 143         pht(
 144           'Expected "newExternalCursorStringForResult()"  in class "%s" to '.
 145           'return a string, but got "%s".',
 146           get_class($this),
 147           phutil_describe_type($cursor)));
 148     }
 149
 150     return $cursor;
 151   }
 152
 153   final protected function getExternalCursorString() {
 154     return $this->externalCursorString;
 155   }
 156
 157   private function setExternalCursorString($external_cursor) {
 158     $this->externalCursorString = $external_cursor;
 159     return $this;
 160   }
 161
 162   final protected function getIsQueryOrderReversed() {
 163     return $this->isQueryOrderReversed;
 164   }
 165
 166   final protected function setIsQueryOrderReversed($is_reversed) {
 167     $this->isQueryOrderReversed = $is_reversed;
 168     return $this;
 169   }
 170
 171   private function getInternalCursorObject() {
 172     return $this->internalCursorObject;
 173   }
 174
 175   private function setInternalCursorObject(
 176     PhabricatorQueryCursor $cursor) {
 177     $this->internalCursorObject = $cursor;
 178     return $this;
 179   }
 180
 181   private function getInternalCursorFromExternalCursor(
 182     $cursor_string) {
 183
 184     $cursor_object = $this->newInternalCursorFromExternalCursor($cursor_string);
 185
 186     if (!($cursor_object instanceof PhabricatorQueryCursor)) {
 187       throw new Exception(
 188         pht(
 189           'Expected "newInternalCursorFromExternalCursor()" to return an '.
 190           'object of class "PhabricatorQueryCursor", but got "%s" (in '.
 191           'class "%s").',
 192           phutil_describe_type($cursor_object),
 193           get_class($this)));
 194     }
 195
 196     return $cursor_object;
 197   }
 198
 199   private function getPagingMapFromCursorObject(
 200     PhabricatorQueryCursor $cursor,
 201     array $keys) {
 202
 203     $map = $this->newPagingMapFromCursorObject($cursor, $keys);
 204
 205     if (!is_array($map)) {
 206       throw new Exception(
 207         pht(
 208           'Expected "newPagingMapFromCursorObject()" to return a map of '.
 209           'paging values, but got "%s" (in class "%s").',
 210           phutil_describe_type($map),
 211           get_class($this)));
 212     }
 213
 214     if ($this->supportsFerretEngine()) {
 215       if ($this->hasFerretOrder()) {
 216         $map += array(
 217           'rank' =>
 218             $cursor->getRawRowProperty(self::FULLTEXT_RANK),
 219           'fulltext-modified' =>
 220             $cursor->getRawRowProperty(self::FULLTEXT_MODIFIED),
 221           'fulltext-created' =>
 222             $cursor->getRawRowProperty(self::FULLTEXT_CREATED),
 223         );
 224       }
 225     }
 226
 227     foreach ($keys as $key) {
 228       if (!array_key_exists($key, $map)) {
 229         throw new Exception(
 230           pht(
 231             'Map returned by "newPagingMapFromCursorObject()" in class "%s" '.
 232             'omits required key "%s".',
 233             get_class($this),
 234             $key));
 235       }
 236     }
 237
 238     return $map;
 239   }
 240
 241   final protected function nextPage(array $page) {
 242     if (!$page) {
 243       return;
 244     }
 245
 246     $cursor = id(new PhabricatorQueryCursor())
 247       ->setObject(last($page));
 248
 249     if ($this->rawCursorRow) {
 250       $cursor->setRawRow($this->rawCursorRow);
 251     }
 252
 253     $this->setInternalCursorObject($cursor);
 254   }
 255
 256   final public function getFerretMetadata() {
 257     if (!$this->supportsFerretEngine()) {
 258       throw new Exception(
 259         pht(
 260           'Unable to retrieve Ferret engine metadata, this class ("%s") does '.
 261           'not support the Ferret engine.',
 262           get_class($this)));
 263     }
 264
 265     return $this->ferretMetadata;
 266   }
 267
 268   protected function loadStandardPage(PhabricatorLiskDAO $table) {
 269     $rows = $this->loadStandardPageRows($table);
 270     return $table->loadAllFromArray($rows);
 271   }
 272
 273   protected function loadStandardPageRows(PhabricatorLiskDAO $table) {
 274     $conn = $table->establishConnection('r');
 275     return $this->loadStandardPageRowsWithConnection(
 276       $conn,
 277       $table->getTableName());
 278   }
 279
 280   protected function loadStandardPageRowsWithConnection(
 281     AphrontDatabaseConnection $conn,
 282     $table_name) {
 283
 284     $query = $this->buildStandardPageQuery($conn, $table_name);
 285
 286     $rows = queryfx_all($conn, '%Q', $query);
 287     $rows = $this->didLoadRawRows($rows);
 288
 289     return $rows;
 290   }
 291
 292   protected function buildStandardPageQuery(
 293     AphrontDatabaseConnection $conn,
 294     $table_name) {
 295
 296     $table_alias = $this->getPrimaryTableAlias();
 297     if ($table_alias === null) {
 298       $table_alias = qsprintf($conn, '');
 299     } else {
 300       $table_alias = qsprintf($conn, '%T', $table_alias);
 301     }
 302
 303     return qsprintf(
 304       $conn,
 305       '%Q FROM %T %Q %Q %Q %Q %Q %Q %Q',
 306       $this->buildSelectClause($conn),
 307       $table_name,
 308       $table_alias,
 309       $this->buildJoinClause($conn),
 310       $this->buildWhereClause($conn),
 311       $this->buildGroupClause($conn),
 312       $this->buildHavingClause($conn),
 313       $this->buildOrderClause($conn),
 314       $this->buildLimitClause($conn));
 315   }
 316
 317   protected function didLoadRawRows(array $rows) {
 318     $this->rawCursorRow = last($rows);
 319
 320     if ($this->ferretEngine) {
 321       foreach ($rows as $row) {
 322         $phid = $row['phid'];
 323
 324         $metadata = id(new PhabricatorFerretMetadata())
 325           ->setPHID($phid)
 326           ->setEngine($this->ferretEngine)
 327           ->setRelevance(idx($row, self::FULLTEXT_RANK));
 328
 329         $this->ferretMetadata[$phid] = $metadata;
 330
 331         unset($row[self::FULLTEXT_RANK]);
 332         unset($row[self::FULLTEXT_MODIFIED]);
 333         unset($row[self::FULLTEXT_CREATED]);
 334       }
 335     }
 336
 337     return $rows;
 338   }
 339
 340   final protected function buildLimitClause(AphrontDatabaseConnection $conn) {
 341     if ($this->shouldLimitResults()) {
 342       $limit = $this->getRawResultLimit();
 343       if ($limit) {
 344         return qsprintf($conn, 'LIMIT %d', $limit);
 345       }
 346     }
 347
 348     return qsprintf($conn, '');
 349   }
 350
 351   protected function shouldLimitResults() {
 352     return true;
 353   }
 354
 355   final protected function didLoadResults(array $results) {
 356     if ($this->getIsQueryOrderReversed()) {
 357       $results = array_reverse($results, $preserve_keys = true);
 358     }
 359
 360     return $results;
 361   }
 362
 363   final public function newIterator() {
 364     return new PhabricatorQueryIterator($this);
 365   }
 366
 367   final public function executeWithCursorPager(AphrontCursorPagerView $pager) {
 368     $limit = $pager->getPageSize();
 369
 370     $this->setLimit($limit + 1);
 371
 372     if (strlen($pager->getAfterID())) {
 373       $this->setExternalCursorString($pager->getAfterID());
 374     } else if ($pager->getBeforeID()) {
 375       $this->setExternalCursorString($pager->getBeforeID());
 376       $this->setIsQueryOrderReversed(true);
 377     }
 378
 379     $results = $this->execute();
 380     $count = count($results);
 381
 382     $sliced_results = $pager->sliceResults($results);
 383     if ($sliced_results) {
 384
 385       // If we have results, generate external-facing cursors from the visible
 386       // results. This stops us from leaking any internal details about objects
 387       // which we loaded but which were not visible to the viewer.
 388
 389       if ($pager->getBeforeID() || ($count > $limit)) {
 390         $last_object = last($sliced_results);
 391         $cursor = $this->getExternalCursorStringForResult($last_object);
 392         $pager->setNextPageID($cursor);
 393       }
 394
 395       if ($pager->getAfterID() ||
 396          ($pager->getBeforeID() && ($count > $limit))) {
 397         $head_object = head($sliced_results);
 398         $cursor = $this->getExternalCursorStringForResult($head_object);
 399         $pager->setPrevPageID($cursor);
 400       }
 401     }
 402
 403     return $sliced_results;
 404   }
 405
 406
 407   /**
 408    * Return the alias this query uses to identify the primary table.
 409    *
 410    * Some automatic query constructions may need to be qualified with a table
 411    * alias if the query performs joins which make column names ambiguous. If
 412    * this is the case, return the alias for the primary table the query
 413    * uses; generally the object table which has `id` and `phid` columns.
 414    *
 415    * @return string Alias for the primary table.
 416    */
 417   protected function getPrimaryTableAlias() {
 418     return null;
 419   }
 420
 421   public function newResultObject() {
 422     return null;
 423   }
 424
 425
 426 /* -(  Building Query Clauses  )--------------------------------------------- */
 427
 428
 429   /**
 430    * @task clauses
 431    */
 432   protected function buildSelectClause(AphrontDatabaseConnection $conn) {
 433     $parts = $this->buildSelectClauseParts($conn);
 434     return $this->formatSelectClause($conn, $parts);
 435   }
 436
 437
 438   /**
 439    * @task clauses
 440    */
 441   protected function buildSelectClauseParts(AphrontDatabaseConnection $conn) {
 442     $select = array();
 443
 444     $alias = $this->getPrimaryTableAlias();
 445     if ($alias) {
 446       $select[] = qsprintf($conn, '%T.*', $alias);
 447     } else {
 448       $select[] = qsprintf($conn, '*');
 449     }
 450
 451     $select[] = $this->buildEdgeLogicSelectClause($conn);
 452     $select[] = $this->buildFerretSelectClause($conn);
 453
 454     return $select;
 455   }
 456
 457
 458   /**
 459    * @task clauses
 460    */
 461   protected function buildJoinClause(AphrontDatabaseConnection $conn) {
 462     $joins = $this->buildJoinClauseParts($conn);
 463     return $this->formatJoinClause($conn, $joins);
 464   }
 465
 466
 467   /**
 468    * @task clauses
 469    */
 470   protected function buildJoinClauseParts(AphrontDatabaseConnection $conn) {
 471     $joins = array();
 472     $joins[] = $this->buildEdgeLogicJoinClause($conn);
 473     $joins[] = $this->buildApplicationSearchJoinClause($conn);
 474     $joins[] = $this->buildNgramsJoinClause($conn);
 475     $joins[] = $this->buildFerretJoinClause($conn);
 476     return $joins;
 477   }
 478
 479
 480   /**
 481    * @task clauses
 482    */
 483   protected function buildWhereClause(AphrontDatabaseConnection $conn) {
 484     $where = $this->buildWhereClauseParts($conn);
 485     return $this->formatWhereClause($conn, $where);
 486   }
 487
 488
 489   /**
 490    * @task clauses
 491    */
 492   protected function buildWhereClauseParts(AphrontDatabaseConnection $conn) {
 493     $where = array();
 494     $where[] = $this->buildPagingWhereClause($conn);
 495     $where[] = $this->buildEdgeLogicWhereClause($conn);
 496     $where[] = $this->buildSpacesWhereClause($conn);
 497     $where[] = $this->buildNgramsWhereClause($conn);
 498     $where[] = $this->buildFerretWhereClause($conn);
 499     $where[] = $this->buildApplicationSearchWhereClause($conn);
 500     return $where;
 501   }
 502
 503
 504   /**
 505    * @task clauses
 506    */
 507   protected function buildHavingClause(AphrontDatabaseConnection $conn) {
 508     $having = $this->buildHavingClauseParts($conn);
 509     $having[] = $this->buildPagingHavingClause($conn);
 510     return $this->formatHavingClause($conn, $having);
 511   }
 512
 513
 514   /**
 515    * @task clauses
 516    */
 517   protected function buildHavingClauseParts(AphrontDatabaseConnection $conn) {
 518     $having = array();
 519     $having[] = $this->buildEdgeLogicHavingClause($conn);
 520     return $having;
 521   }
 522
 523
 524   /**
 525    * @task clauses
 526    */
 527   protected function buildGroupClause(AphrontDatabaseConnection $conn) {
 528     if (!$this->shouldGroupQueryResultRows()) {
 529       return qsprintf($conn, '');
 530     }
 531
 532     return qsprintf(
 533       $conn,
 534       'GROUP BY %Q',
 535       $this->getApplicationSearchObjectPHIDColumn($conn));
 536   }
 537
 538
 539   /**
 540    * @task clauses
 541    */
 542   protected function shouldGroupQueryResultRows() {
 543     if ($this->shouldGroupEdgeLogicResultRows()) {
 544       return true;
 545     }
 546
 547     if ($this->getApplicationSearchMayJoinMultipleRows()) {
 548       return true;
 549     }
 550
 551     if ($this->shouldGroupNgramResultRows()) {
 552       return true;
 553     }
 554
 555     if ($this->shouldGroupFerretResultRows()) {
 556       return true;
 557     }
 558
 559     return false;
 560   }
 561
 562
 563
 564 /* -(  Paging  )------------------------------------------------------------- */
 565
 566
 567   private function buildPagingWhereClause(AphrontDatabaseConnection $conn) {
 568     if ($this->shouldPageWithHavingClause()) {
 569       return null;
 570     }
 571
 572     return $this->buildPagingClause($conn);
 573   }
 574
 575   private function buildPagingHavingClause(AphrontDatabaseConnection $conn) {
 576     if (!$this->shouldPageWithHavingClause()) {
 577       return null;
 578     }
 579
 580     return $this->buildPagingClause($conn);
 581   }
 582
 583   private function shouldPageWithHavingClause() {
 584     // If any of the paging conditions reference dynamic columns, we need to
 585     // put the paging conditions in a "HAVING" clause instead of a "WHERE"
 586     // clause.
 587
 588     // For example, this happens when paging on the Ferret "rank" column,
 589     // since the "rank" value is computed dynamically in the SELECT statement.
 590
 591     $orderable = $this->getOrderableColumns();
 592     $vector = $this->getOrderVector();
 593
 594     foreach ($vector as $order) {
 595       $key = $order->getOrderKey();
 596       $column = $orderable[$key];
 597
 598       if (!empty($column['having'])) {
 599         return true;
 600       }
 601     }
 602
 603     return false;
 604   }
 605
 606   /**
 607    * @task paging
 608    */
 609   protected function buildPagingClause(AphrontDatabaseConnection $conn) {
 610     $orderable = $this->getOrderableColumns();
 611     $vector = $this->getQueryableOrderVector();
 612
 613     // If we don't have a cursor object yet, it means we're trying to load
 614     // the first result page. We may need to build a cursor object from the
 615     // external string, or we may not need a paging clause yet.
 616     $cursor_object = $this->getInternalCursorObject();
 617     if (!$cursor_object) {
 618       $external_cursor = $this->getExternalCursorString();
 619       if ($external_cursor !== null) {
 620         $cursor_object = $this->getInternalCursorFromExternalCursor(
 621           $external_cursor);
 622       }
 623     }
 624
 625     // If we still don't have a cursor object, this is the first result page
 626     // and we aren't paging it. We don't need to build a paging clause.
 627     if (!$cursor_object) {
 628       return qsprintf($conn, '');
 629     }
 630
 631     $reversed = $this->getIsQueryOrderReversed();
 632
 633     $keys = array();
 634     foreach ($vector as $order) {
 635       $keys[] = $order->getOrderKey();
 636     }
 637     $keys = array_fuse($keys);
 638
 639     $value_map = $this->getPagingMapFromCursorObject(
 640       $cursor_object,
 641       $keys);
 642
 643     $columns = array();
 644     foreach ($vector as $order) {
 645       $key = $order->getOrderKey();
 646
 647       $column = $orderable[$key];
 648       $column['value'] = $value_map[$key];
 649
 650       // If the vector component is reversed, we need to reverse whatever the
 651       // order of the column is.
 652       if ($order->getIsReversed()) {
 653         $column['reverse'] = !idx($column, 'reverse', false);
 654       }
 655
 656       $columns[] = $column;
 657     }
 658
 659     return $this->buildPagingClauseFromMultipleColumns(
 660       $conn,
 661       $columns,
 662       array(
 663         'reversed' => $reversed,
 664       ));
 665   }
 666
 667
 668   /**
 669    * Simplifies the task of constructing a paging clause across multiple
 670    * columns. In the general case, this looks like:
 671    *
 672    *   A > a OR (A = a AND B > b) OR (A = a AND B = b AND C > c)
 673    *
 674    * To build a clause, specify the name, type, and value of each column
 675    * to include:
 676    *
 677    *   $this->buildPagingClauseFromMultipleColumns(
 678    *     $conn_r,
 679    *     array(
 680    *       array(
 681    *         'table' => 't',
 682    *         'column' => 'title',
 683    *         'type' => 'string',
 684    *         'value' => $cursor->getTitle(),
 685    *         'reverse' => true,
 686    *       ),
 687    *       array(
 688    *         'table' => 't',
 689    *         'column' => 'id',
 690    *         'type' => 'int',
 691    *         'value' => $cursor->getID(),
 692    *       ),
 693    *     ),
 694    *     array(
 695    *       'reversed' => $is_reversed,
 696    *     ));
 697    *
 698    * This method will then return a composable clause for inclusion in WHERE.
 699    *
 700    * @param AphrontDatabaseConnection Connection query will execute on.
 701    * @param list<map> Column description dictionaries.
 702    * @param map Additional construction options.
 703    * @return string Query clause.
 704    * @task paging
 705    */
 706   final protected function buildPagingClauseFromMultipleColumns(
 707     AphrontDatabaseConnection $conn,
 708     array $columns,
 709     array $options) {
 710
 711     foreach ($columns as $column) {
 712       PhutilTypeSpec::checkMap(
 713         $column,
 714         array(
 715           'table' => 'optional string|null',
 716           'column' => 'string',
 717           'value' => 'wild',
 718           'type' => 'string',
 719           'reverse' => 'optional bool',
 720           'unique' => 'optional bool',
 721           'null' => 'optional string|null',
 722           'requires-ferret' => 'optional bool',
 723           'having' => 'optional bool',
 724         ));
 725     }
 726
 727     PhutilTypeSpec::checkMap(
 728       $options,
 729       array(
 730         'reversed' => 'optional bool',
 731       ));
 732
 733     $is_query_reversed = idx($options, 'reversed', false);
 734
 735     $clauses = array();
 736     $accumulated = array();
 737     $last_key = last_key($columns);
 738     foreach ($columns as $key => $column) {
 739       $type = $column['type'];
 740
 741       $null = idx($column, 'null');
 742       if ($column['value'] === null) {
 743         if ($null) {
 744           $value = null;
 745         } else {
 746           throw new Exception(
 747             pht(
 748               'Column "%s" has null value, but does not specify a null '.
 749               'behavior.',
 750               $key));
 751         }
 752       } else {
 753         switch ($type) {
 754           case 'int':
 755             $value = qsprintf($conn, '%d', $column['value']);
 756             break;
 757           case 'float':
 758             $value = qsprintf($conn, '%f', $column['value']);
 759             break;
 760           case 'string':
 761             $value = qsprintf($conn, '%s', $column['value']);
 762             break;
 763           default:
 764             throw new Exception(
 765               pht(
 766                 'Column "%s" has unknown column type "%s".',
 767                 $column['column'],
 768                 $type));
 769         }
 770       }
 771
 772       $is_column_reversed = idx($column, 'reverse', false);
 773       $reverse = ($is_query_reversed xor $is_column_reversed);
 774
 775       $clause = $accumulated;
 776
 777       $table_name = idx($column, 'table');
 778       $column_name = $column['column'];
 779       if ($table_name !== null) {
 780         $field = qsprintf($conn, '%T.%T', $table_name, $column_name);
 781       } else {
 782         $field = qsprintf($conn, '%T', $column_name);
 783       }
 784
 785       $parts = array();
 786       if ($null) {
 787         $can_page_if_null = ($null === 'head');
 788         $can_page_if_nonnull = ($null === 'tail');
 789
 790         if ($reverse) {
 791           $can_page_if_null = !$can_page_if_null;
 792           $can_page_if_nonnull = !$can_page_if_nonnull;
 793         }
 794
 795         $subclause = null;
 796         if ($can_page_if_null && $value === null) {
 797           $parts[] = qsprintf(
 798             $conn,
 799             '(%Q IS NOT NULL)',
 800             $field);
 801         } else if ($can_page_if_nonnull && $value !== null) {
 802           $parts[] = qsprintf(
 803             $conn,
 804             '(%Q IS NULL)',
 805             $field);
 806         }
 807       }
 808
 809       if ($value !== null) {
 810         $parts[] = qsprintf(
 811           $conn,
 812           '%Q %Q %Q',
 813           $field,
 814           $reverse ? qsprintf($conn, '>') : qsprintf($conn, '<'),
 815           $value);
 816       }
 817
 818       if ($parts) {
 819         $clause[] = qsprintf($conn, '%LO', $parts);
 820       }
 821
 822       if ($clause) {
 823         $clauses[] = qsprintf($conn, '%LA', $clause);
 824       }
 825
 826       if ($value === null) {
 827         $accumulated[] = qsprintf(
 828           $conn,
 829           '%Q IS NULL',
 830           $field);
 831       } else {
 832         $accumulated[] = qsprintf(
 833           $conn,
 834           '%Q = %Q',
 835           $field,
 836           $value);
 837       }
 838     }
 839
 840     if ($clauses) {
 841       return qsprintf($conn, '%LO', $clauses);
 842     }
 843
 844     return qsprintf($conn, '');
 845   }
 846
 847
 848 /* -(  Result Ordering  )---------------------------------------------------- */
 849
 850
 851   /**
 852    * Select a result ordering.
 853    *
 854    * This is a high-level method which selects an ordering from a predefined
 855    * list of builtin orders, as provided by @{method:getBuiltinOrders}. These
 856    * options are user-facing and not exhaustive, but are generally convenient
 857    * and meaningful.
 858    *
 859    * You can also use @{method:setOrderVector} to specify a low-level ordering
 860    * across individual orderable columns. This offers greater control but is
 861    * also more involved.
 862    *
 863    * @param string Key of a builtin order supported by this query.
 864    * @return this
 865    * @task order
 866    */
 867   public function setOrder($order) {
 868     $aliases = $this->getBuiltinOrderAliasMap();
 869
 870     if (empty($aliases[$order])) {
 871       throw new Exception(
 872         pht(
 873           'Query "%s" does not support a builtin order "%s". Supported orders '.
 874           'are: %s.',
 875           get_class($this),
 876           $order,
 877           implode(', ', array_keys($aliases))));
 878     }
 879
 880     $this->builtinOrder = $aliases[$order];
 881     $this->orderVector = null;
 882
 883     return $this;
 884   }
 885
 886
 887   /**
 888    * Set a grouping order to apply before primary result ordering.
 889    *
 890    * This allows you to preface the query order vector with additional orders,
 891    * so you can effect "group by" queries while still respecting "order by".
 892    *
 893    * This is a high-level method which works alongside @{method:setOrder}. For
 894    * lower-level control over order vectors, use @{method:setOrderVector}.
 895    *
 896    * @param PhabricatorQueryOrderVector|list<string> List of order keys.
 897    * @return this
 898    * @task order
 899    */
 900   public function setGroupVector($vector) {
 901     $this->groupVector = $vector;
 902     $this->orderVector = null;
 903
 904     return $this;
 905   }
 906
 907
 908   /**
 909    * Get builtin orders for this class.
 910    *
 911    * In application UIs, we want to be able to present users with a small
 912    * selection of meaningful order options (like "Order by Title") rather than
 913    * an exhaustive set of column ordering options.
 914    *
 915    * Meaningful user-facing orders are often really orders across multiple
 916    * columns: for example, a "title" ordering is usually implemented as a
 917    * "title, id" ordering under the hood.
 918    *
 919    * Builtin orders provide a mapping from convenient, understandable
 920    * user-facing orders to implementations.
 921    *
 922    * A builtin order should provide these keys:
 923    *
 924    *   - `vector` (`list<string>`): The actual order vector to use.
 925    *   - `name` (`string`): Human-readable order name.
 926    *
 927    * @return map<string, wild> Map from builtin order keys to specification.
 928    * @task order
 929    */
 930   public function getBuiltinOrders() {
 931     $orders = array(
 932       'newest' => array(
 933         'vector' => array('id'),
 934         'name' => pht('Creation (Newest First)'),
 935         'aliases' => array('created'),
 936       ),
 937       'oldest' => array(
 938         'vector' => array('-id'),
 939         'name' => pht('Creation (Oldest First)'),
 940       ),
 941     );
 942
 943     $object = $this->newResultObject();
 944     if ($object instanceof PhabricatorCustomFieldInterface) {
 945       $list = PhabricatorCustomField::getObjectFields(
 946         $object,
 947         PhabricatorCustomField::ROLE_APPLICATIONSEARCH);
 948       foreach ($list->getFields() as $field) {
 949         $index = $field->buildOrderIndex();
 950         if (!$index) {
 951           continue;
 952         }
 953
 954         $legacy_key = 'custom:'.$field->getFieldKey();
 955         $modern_key = $field->getModernFieldKey();
 956
 957         $orders[$modern_key] = array(
 958           'vector' => array($modern_key, 'id'),
 959           'name' => $field->getFieldName(),
 960           'aliases' => array($legacy_key),
 961         );
 962
 963         $orders['-'.$modern_key] = array(
 964           'vector' => array('-'.$modern_key, '-id'),
 965           'name' => pht('%s (Reversed)', $field->getFieldName()),
 966         );
 967       }
 968     }
 969
 970     if ($this->supportsFerretEngine()) {
 971       $orders['relevance'] = array(
 972         'vector' => array('rank', 'fulltext-modified', 'id'),
 973         'name' => pht('Relevance'),
 974       );
 975     }
 976
 977     return $orders;
 978   }
 979
 980   public function getBuiltinOrderAliasMap() {
 981     $orders = $this->getBuiltinOrders();
 982
 983     $map = array();
 984     foreach ($orders as $key => $order) {
 985       $keys = array();
 986       $keys[] = $key;
 987       foreach (idx($order, 'aliases', array()) as $alias) {
 988         $keys[] = $alias;
 989       }
 990
 991       foreach ($keys as $alias) {
 992         if (isset($map[$alias])) {
 993           throw new Exception(
 994             pht(
 995               'Two builtin orders ("%s" and "%s") define the same key or '.
 996               'alias ("%s"). Each order alias and key must be unique and '.
 997               'identify a single order.',
 998               $key,
 999               $map[$alias],
1000               $alias));
1001         }
1002         $map[$alias] = $key;
1003       }
1004     }
1005
1006     return $map;
1007   }
1008
1009
1010   /**
1011    * Set a low-level column ordering.
1012    *
1013    * This is a low-level method which offers granular control over column
1014    * ordering. In most cases, applications can more easily use
1015    * @{method:setOrder} to choose a high-level builtin order.
1016    *
1017    * To set an order vector, specify a list of order keys as provided by
1018    * @{method:getOrderableColumns}.
1019    *
1020    * @param PhabricatorQueryOrderVector|list<string> List of order keys.
1021    * @return this
1022    * @task order
1023    */
1024   public function setOrderVector($vector) {
1025     $vector = PhabricatorQueryOrderVector::newFromVector($vector);
1026
1027     $orderable = $this->getOrderableColumns();
1028
1029     // Make sure that all the components identify valid columns.
1030     $unique = array();
1031     foreach ($vector as $order) {
1032       $key = $order->getOrderKey();
1033       if (empty($orderable[$key])) {
1034         $valid = implode(', ', array_keys($orderable));
1035         throw new Exception(
1036           pht(
1037             'This query ("%s") does not support sorting by order key "%s". '.
1038             'Supported orders are: %s.',
1039             get_class($this),
1040             $key,
1041             $valid));
1042       }
1043
1044       $unique[$key] = idx($orderable[$key], 'unique', false);
1045     }
1046
1047     // Make sure that the last column is unique so that this is a strong
1048     // ordering which can be used for paging.
1049     $last = last($unique);
1050     if ($last !== true) {
1051       throw new Exception(
1052         pht(
1053           'Order vector "%s" is invalid: the last column in an order must '.
1054           'be a column with unique values, but "%s" is not unique.',
1055           $vector->getAsString(),
1056           last_key($unique)));
1057     }
1058
1059     // Make sure that other columns are not unique; an ordering like "id, name"
1060     // does not make sense because only "id" can ever have an effect.
1061     array_pop($unique);
1062     foreach ($unique as $key => $is_unique) {
1063       if ($is_unique) {
1064         throw new Exception(
1065           pht(
1066             'Order vector "%s" is invalid: only the last column in an order '.
1067             'may be unique, but "%s" is a unique column and not the last '.
1068             'column in the order.',
1069             $vector->getAsString(),
1070             $key));
1071       }
1072     }
1073
1074     $this->orderVector = $vector;
1075     return $this;
1076   }
1077
1078
1079   /**
1080    * Get the effective order vector.
1081    *
1082    * @return PhabricatorQueryOrderVector Effective vector.
1083    * @task order
1084    */
1085   protected function getOrderVector() {
1086     if (!$this->orderVector) {
1087       if ($this->builtinOrder !== null) {
1088         $builtin_order = idx($this->getBuiltinOrders(), $this->builtinOrder);
1089         $vector = $builtin_order['vector'];
1090       } else {
1091         $vector = $this->getDefaultOrderVector();
1092       }
1093
1094       if ($this->groupVector) {
1095         $group = PhabricatorQueryOrderVector::newFromVector($this->groupVector);
1096         $group->appendVector($vector);
1097         $vector = $group;
1098       }
1099
1100       $vector = PhabricatorQueryOrderVector::newFromVector($vector);
1101
1102       // We call setOrderVector() here to apply checks to the default vector.
1103       // This catches any errors in the implementation.
1104       $this->setOrderVector($vector);
1105     }
1106
1107     return $this->orderVector;
1108   }
1109
1110
1111   /**
1112    * @task order
1113    */
1114   protected function getDefaultOrderVector() {
1115     return array('id');
1116   }
1117
1118
1119   /**
1120    * @task order
1121    */
1122   public function getOrderableColumns() {
1123     $cache = PhabricatorCaches::getRequestCache();
1124     $class = get_class($this);
1125     $cache_key = 'query.orderablecolumns.'.$class;
1126
1127     $columns = $cache->getKey($cache_key);
1128     if ($columns !== null) {
1129       return $columns;
1130     }
1131
1132     $columns = array(
1133       'id' => array(
1134         'table' => $this->getPrimaryTableAlias(),
1135         'column' => 'id',
1136         'reverse' => false,
1137         'type' => 'int',
1138         'unique' => true,
1139       ),
1140     );
1141
1142     $object = $this->newResultObject();
1143     if ($object instanceof PhabricatorCustomFieldInterface) {
1144       $list = PhabricatorCustomField::getObjectFields(
1145         $object,
1146         PhabricatorCustomField::ROLE_APPLICATIONSEARCH);
1147       foreach ($list->getFields() as $field) {
1148         $index = $field->buildOrderIndex();
1149         if (!$index) {
1150           continue;
1151         }
1152
1153         $digest = $field->getFieldIndex();
1154
1155         $key = $field->getModernFieldKey();
1156
1157         $columns[$key] = array(
1158           'table' => 'appsearch_order_'.$digest,
1159           'column' => 'indexValue',
1160           'type' => $index->getIndexValueType(),
1161           'null' => 'tail',
1162           'customfield' => true,
1163           'customfield.index.table' => $index->getTableName(),
1164           'customfield.index.key' => $digest,
1165         );
1166       }
1167     }
1168
1169     if ($this->supportsFerretEngine()) {
1170       $columns['rank'] = array(
1171         'table' => null,
1172         'column' => self::FULLTEXT_RANK,
1173         'type' => 'int',
1174         'requires-ferret' => true,
1175         'having' => true,
1176       );
1177       $columns['fulltext-created'] = array(
1178         'table' => null,
1179         'column' => self::FULLTEXT_CREATED,
1180         'type' => 'int',
1181         'requires-ferret' => true,
1182       );
1183       $columns['fulltext-modified'] = array(
1184         'table' => null,
1185         'column' => self::FULLTEXT_MODIFIED,
1186         'type' => 'int',
1187         'requires-ferret' => true,
1188       );
1189     }
1190
1191     $cache->setKey($cache_key, $columns);
1192
1193     return $columns;
1194   }
1195
1196
1197   /**
1198    * @task order
1199    */
1200   final protected function buildOrderClause(
1201     AphrontDatabaseConnection $conn,
1202     $for_union = false) {
1203
1204     $orderable = $this->getOrderableColumns();
1205     $vector = $this->getQueryableOrderVector();
1206
1207     $parts = array();
1208     foreach ($vector as $order) {
1209       $part = $orderable[$order->getOrderKey()];
1210
1211       if ($order->getIsReversed()) {
1212         $part['reverse'] = !idx($part, 'reverse', false);
1213       }
1214       $parts[] = $part;
1215     }
1216
1217     return $this->formatOrderClause($conn, $parts, $for_union);
1218   }
1219
1220   /**
1221    * @task order
1222    */
1223   private function getQueryableOrderVector() {
1224     $vector = $this->getOrderVector();
1225     $orderable = $this->getOrderableColumns();
1226
1227     $keep = array();
1228     foreach ($vector as $order) {
1229       $column = $orderable[$order->getOrderKey()];
1230
1231       // If this is a Ferret fulltext column but the query doesn't actually
1232       // have a fulltext query, we'll skip most of the Ferret stuff and won't
1233       // actually have the columns in the result set. Just skip them.
1234       if (!empty($column['requires-ferret'])) {
1235         if (!$this->getFerretTokens()) {
1236           continue;
1237         }
1238       }
1239
1240       $keep[] = $order->getAsScalar();
1241     }
1242
1243     return PhabricatorQueryOrderVector::newFromVector($keep);
1244   }
1245
1246   /**
1247    * @task order
1248    */
1249   protected function formatOrderClause(
1250     AphrontDatabaseConnection $conn,
1251     array $parts,
1252     $for_union = false) {
1253
1254     $is_query_reversed = $this->getIsQueryOrderReversed();
1255
1256     $sql = array();
1257     foreach ($parts as $key => $part) {
1258       $is_column_reversed = !empty($part['reverse']);
1259
1260       $descending = true;
1261       if ($is_query_reversed) {
1262         $descending = !$descending;
1263       }
1264
1265       if ($is_column_reversed) {
1266         $descending = !$descending;
1267       }
1268
1269       $table = idx($part, 'table');
1270
1271       // When we're building an ORDER BY clause for a sequence of UNION
1272       // statements, we can't refer to tables from the subqueries.
1273       if ($for_union) {
1274         $table = null;
1275       }
1276
1277       $column = $part['column'];
1278
1279       if ($table !== null) {
1280         $field = qsprintf($conn, '%T.%T', $table, $column);
1281       } else {
1282         $field = qsprintf($conn, '%T', $column);
1283       }
1284
1285       $null = idx($part, 'null');
1286       if ($null) {
1287         switch ($null) {
1288           case 'head':
1289             $null_field = qsprintf($conn, '(%Q IS NULL)', $field);
1290             break;
1291           case 'tail':
1292             $null_field = qsprintf($conn, '(%Q IS NOT NULL)', $field);
1293             break;
1294           default:
1295             throw new Exception(
1296               pht(
1297                 'NULL value "%s" is invalid. Valid values are "head" and '.
1298                 '"tail".',
1299                 $null));
1300         }
1301
1302         if ($descending) {
1303           $sql[] = qsprintf($conn, '%Q DESC', $null_field);
1304         } else {
1305           $sql[] = qsprintf($conn, '%Q ASC', $null_field);
1306         }
1307       }
1308
1309       if ($descending) {
1310         $sql[] = qsprintf($conn, '%Q DESC', $field);
1311       } else {
1312         $sql[] = qsprintf($conn, '%Q ASC', $field);
1313       }
1314     }
1315
1316     return qsprintf($conn, 'ORDER BY %LQ', $sql);
1317   }
1318
1319
1320 /* -(  Application Search  )------------------------------------------------- */
1321
1322
1323   /**
1324    * Constrain the query with an ApplicationSearch index, requiring field values
1325    * contain at least one of the values in a set.
1326    *
1327    * This constraint can build the most common types of queries, like:
1328    *
1329    *   - Find users with shirt sizes "X" or "XL".
1330    *   - Find shoes with size "13".
1331    *
1332    * @param PhabricatorCustomFieldIndexStorage Table where the index is stored.
1333    * @param string|list<string> One or more values to filter by.
1334    * @return this
1335    * @task appsearch
1336    */
1337   public function withApplicationSearchContainsConstraint(
1338     PhabricatorCustomFieldIndexStorage $index,
1339     $value) {
1340
1341     $values = (array)$value;
1342
1343     $data_values = array();
1344     $constraint_values = array();
1345     foreach ($values as $value) {
1346       if ($value instanceof PhabricatorQueryConstraint) {
1347         $constraint_values[] = $value;
1348       } else {
1349         $data_values[] = $value;
1350       }
1351     }
1352
1353     $alias = 'appsearch_'.count($this->applicationSearchConstraints);
1354
1355     $this->applicationSearchConstraints[] = array(
1356       'type'  => $index->getIndexValueType(),
1357       'cond'  => '=',
1358       'table' => $index->getTableName(),
1359       'index' => $index->getIndexKey(),
1360       'alias' => $alias,
1361       'value' => $values,
1362       'data' => $data_values,
1363       'constraints' => $constraint_values,
1364     );
1365
1366     return $this;
1367   }
1368
1369
1370   /**
1371    * Constrain the query with an ApplicationSearch index, requiring values
1372    * exist in a given range.
1373    *
1374    * This constraint is useful for expressing date ranges:
1375    *
1376    *   - Find events between July 1st and July 7th.
1377    *
1378    * The ends of the range are inclusive, so a `$min` of `3` and a `$max` of
1379    * `5` will match fields with values `3`, `4`, or `5`. Providing `null` for
1380    * either end of the range will leave that end of the constraint open.
1381    *
1382    * @param PhabricatorCustomFieldIndexStorage Table where the index is stored.
1383    * @param int|null Minimum permissible value, inclusive.
1384    * @param int|null Maximum permissible value, inclusive.
1385    * @return this
1386    * @task appsearch
1387    */
1388   public function withApplicationSearchRangeConstraint(
1389     PhabricatorCustomFieldIndexStorage $index,
1390     $min,
1391     $max) {
1392
1393     $index_type = $index->getIndexValueType();
1394     if ($index_type != 'int') {
1395       throw new Exception(
1396         pht(
1397           'Attempting to apply a range constraint to a field with index type '.
1398           '"%s", expected type "%s".',
1399           $index_type,
1400           'int'));
1401     }
1402
1403     $alias = 'appsearch_'.count($this->applicationSearchConstraints);
1404
1405     $this->applicationSearchConstraints[] = array(
1406       'type' => $index->getIndexValueType(),
1407       'cond' => 'range',
1408       'table' => $index->getTableName(),
1409       'index' => $index->getIndexKey(),
1410       'alias' => $alias,
1411       'value' => array($min, $max),
1412       'data' => null,
1413       'constraints' => null,
1414     );
1415
1416     return $this;
1417   }
1418
1419
1420   /**
1421    * Get the name of the query's primary object PHID column, for constructing
1422    * JOIN clauses. Normally (and by default) this is just `"phid"`, but it may
1423    * be something more exotic.
1424    *
1425    * See @{method:getPrimaryTableAlias} if the column needs to be qualified with
1426    * a table alias.
1427    *
1428    * @param AphrontDatabaseConnection Connection executing queries.
1429    * @return PhutilQueryString Column name.
1430    * @task appsearch
1431    */
1432   protected function getApplicationSearchObjectPHIDColumn(
1433     AphrontDatabaseConnection $conn) {
1434
1435     if ($this->getPrimaryTableAlias()) {
1436       return qsprintf($conn, '%T.phid', $this->getPrimaryTableAlias());
1437     } else {
1438       return qsprintf($conn, 'phid');
1439     }
1440   }
1441
1442
1443   /**
1444    * Determine if the JOINs built by ApplicationSearch might cause each primary
1445    * object to return multiple result rows. Generally, this means the query
1446    * needs an extra GROUP BY clause.
1447    *
1448    * @return bool True if the query may return multiple rows for each object.
1449    * @task appsearch
1450    */
1451   protected function getApplicationSearchMayJoinMultipleRows() {
1452     foreach ($this->applicationSearchConstraints as $constraint) {
1453       $type = $constraint['type'];
1454       $value = $constraint['value'];
1455       $cond = $constraint['cond'];
1456
1457       switch ($cond) {
1458         case '=':
1459           switch ($type) {
1460             case 'string':
1461             case 'int':
1462               if (count($value) > 1) {
1463                 return true;
1464               }
1465               break;
1466             default:
1467               throw new Exception(pht('Unknown index type "%s"!', $type));
1468           }
1469           break;
1470         case 'range':
1471           // NOTE: It's possible to write a custom field where multiple rows
1472           // match a range constraint, but we don't currently ship any in the
1473           // upstream and I can't immediately come up with cases where this
1474           // would make sense.
1475           break;
1476         default:
1477           throw new Exception(pht('Unknown constraint condition "%s"!', $cond));
1478       }
1479     }
1480
1481     return false;
1482   }
1483
1484
1485   /**
1486    * Construct a GROUP BY clause appropriate for ApplicationSearch constraints.
1487    *
1488    * @param AphrontDatabaseConnection Connection executing the query.
1489    * @return string Group clause.
1490    * @task appsearch
1491    */
1492   protected function buildApplicationSearchGroupClause(
1493     AphrontDatabaseConnection $conn) {
1494
1495     if ($this->getApplicationSearchMayJoinMultipleRows()) {
1496       return qsprintf(
1497         $conn,
1498         'GROUP BY %Q',
1499         $this->getApplicationSearchObjectPHIDColumn($conn));
1500     } else {
1501       return qsprintf($conn, '');
1502     }
1503   }
1504
1505
1506   /**
1507    * Construct a JOIN clause appropriate for applying ApplicationSearch
1508    * constraints.
1509    *
1510    * @param AphrontDatabaseConnection Connection executing the query.
1511    * @return string Join clause.
1512    * @task appsearch
1513    */
1514   protected function buildApplicationSearchJoinClause(
1515     AphrontDatabaseConnection $conn) {
1516
1517     $joins = array();
1518     foreach ($this->applicationSearchConstraints as $key => $constraint) {
1519       $table = $constraint['table'];
1520       $alias = $constraint['alias'];
1521       $index = $constraint['index'];
1522       $cond = $constraint['cond'];
1523       $phid_column = $this->getApplicationSearchObjectPHIDColumn($conn);
1524       switch ($cond) {
1525         case '=':
1526           // Figure out whether we need to do a LEFT JOIN or not. We need to
1527           // LEFT JOIN if we're going to select "IS NULL" rows.
1528           $join_type = qsprintf($conn, 'JOIN');
1529           foreach ($constraint['constraints'] as $query_constraint) {
1530             $op = $query_constraint->getOperator();
1531             if ($op === PhabricatorQueryConstraint::OPERATOR_NULL) {
1532               $join_type = qsprintf($conn, 'LEFT JOIN');
1533               break;
1534             }
1535           }
1536
1537           $joins[] = qsprintf(
1538             $conn,
1539             '%Q %T %T ON %T.objectPHID = %Q
1540               AND %T.indexKey = %s',
1541             $join_type,
1542             $table,
1543             $alias,
1544             $alias,
1545             $phid_column,
1546             $alias,
1547             $index);
1548           break;
1549         case 'range':
1550           list($min, $max) = $constraint['value'];
1551           if (($min === null) && ($max === null)) {
1552             // If there's no actual range constraint, just move on.
1553             break;
1554           }
1555
1556           if ($min === null) {
1557             $constraint_clause = qsprintf(
1558               $conn,
1559               '%T.indexValue <= %d',
1560               $alias,
1561               $max);
1562           } else if ($max === null) {
1563             $constraint_clause = qsprintf(
1564               $conn,
1565               '%T.indexValue >= %d',
1566               $alias,
1567               $min);
1568           } else {
1569             $constraint_clause = qsprintf(
1570               $conn,
1571               '%T.indexValue BETWEEN %d AND %d',
1572               $alias,
1573               $min,
1574               $max);
1575           }
1576
1577           $joins[] = qsprintf(
1578             $conn,
1579             'JOIN %T %T ON %T.objectPHID = %Q
1580               AND %T.indexKey = %s
1581               AND (%Q)',
1582             $table,
1583             $alias,
1584             $alias,
1585             $phid_column,
1586             $alias,
1587             $index,
1588             $constraint_clause);
1589           break;
1590         default:
1591           throw new Exception(pht('Unknown constraint condition "%s"!', $cond));
1592       }
1593     }
1594
1595     $phid_column = $this->getApplicationSearchObjectPHIDColumn($conn);
1596     $orderable = $this->getOrderableColumns();
1597
1598     $vector = $this->getOrderVector();
1599     foreach ($vector as $order) {
1600       $spec = $orderable[$order->getOrderKey()];
1601       if (empty($spec['customfield'])) {
1602         continue;
1603       }
1604
1605       $table = $spec['customfield.index.table'];
1606       $alias = $spec['table'];
1607       $key = $spec['customfield.index.key'];
1608
1609       $joins[] = qsprintf(
1610         $conn,
1611         'LEFT JOIN %T %T ON %T.objectPHID = %Q
1612           AND %T.indexKey = %s',
1613         $table,
1614         $alias,
1615         $alias,
1616         $phid_column,
1617         $alias,
1618         $key);
1619     }
1620
1621     if ($joins) {
1622       return qsprintf($conn, '%LJ', $joins);
1623     } else {
1624       return qsprintf($conn, '');
1625     }
1626   }
1627
1628   /**
1629    * Construct a WHERE clause appropriate for applying ApplicationSearch
1630    * constraints.
1631    *
1632    * @param AphrontDatabaseConnection Connection executing the query.
1633    * @return list<string> Where clause parts.
1634    * @task appsearch
1635    */
1636   protected function buildApplicationSearchWhereClause(
1637     AphrontDatabaseConnection $conn) {
1638
1639     $where = array();
1640
1641     foreach ($this->applicationSearchConstraints as $key => $constraint) {
1642       $alias = $constraint['alias'];
1643       $cond = $constraint['cond'];
1644       $type = $constraint['type'];
1645
1646       $data_values = $constraint['data'];
1647       $constraint_values = $constraint['constraints'];
1648
1649       $constraint_parts = array();
1650       switch ($cond) {
1651         case '=':
1652           if ($data_values) {
1653             switch ($type) {
1654               case 'string':
1655                 $constraint_parts[] = qsprintf(
1656                   $conn,
1657                   '%T.indexValue IN (%Ls)',
1658                   $alias,
1659                   $data_values);
1660                 break;
1661               case 'int':
1662                 $constraint_parts[] = qsprintf(
1663                   $conn,
1664                   '%T.indexValue IN (%Ld)',
1665                   $alias,
1666                   $data_values);
1667                 break;
1668               default:
1669                 throw new Exception(pht('Unknown index type "%s"!', $type));
1670             }
1671           }
1672
1673           if ($constraint_values) {
1674             foreach ($constraint_values as $value) {
1675               $op = $value->getOperator();
1676               switch ($op) {
1677                 case PhabricatorQueryConstraint::OPERATOR_NULL:
1678                   $constraint_parts[] = qsprintf(
1679                     $conn,
1680                     '%T.indexValue IS NULL',
1681                     $alias);
1682                   break;
1683                 case PhabricatorQueryConstraint::OPERATOR_ANY:
1684                   $constraint_parts[] = qsprintf(
1685                     $conn,
1686                     '%T.indexValue IS NOT NULL',
1687                     $alias);
1688                   break;
1689                 default:
1690                   throw new Exception(
1691                     pht(
1692                       'No support for applying operator "%s" against '.
1693                       'index of type "%s".',
1694                       $op,
1695                       $type));
1696               }
1697             }
1698           }
1699
1700           if ($constraint_parts) {
1701             $where[] = qsprintf($conn, '%LO', $constraint_parts);
1702           }
1703           break;
1704       }
1705     }
1706
1707     return $where;
1708   }
1709
1710
1711 /* -(  Integration with CustomField  )--------------------------------------- */
1712
1713
1714   /**
1715    * @task customfield
1716    */
1717   protected function getPagingValueMapForCustomFields(
1718     PhabricatorCustomFieldInterface $object) {
1719
1720     // We have to get the current field values on the cursor object.
1721     $fields = PhabricatorCustomField::getObjectFields(
1722       $object,
1723       PhabricatorCustomField::ROLE_APPLICATIONSEARCH);
1724     $fields->setViewer($this->getViewer());
1725     $fields->readFieldsFromStorage($object);
1726
1727     $map = array();
1728     foreach ($fields->getFields() as $field) {
1729       $map['custom:'.$field->getFieldKey()] = $field->getValueForStorage();
1730     }
1731
1732     return $map;
1733   }
1734
1735
1736   /**
1737    * @task customfield
1738    */
1739   protected function isCustomFieldOrderKey($key) {
1740     $prefix = 'custom:';
1741     return !strncmp($key, $prefix, strlen($prefix));
1742   }
1743
1744
1745 /* -(  Ferret  )------------------------------------------------------------- */
1746
1747
1748   public function supportsFerretEngine() {
1749     $object = $this->newResultObject();
1750     return ($object instanceof PhabricatorFerretInterface);
1751   }
1752
1753   public function withFerretQuery(
1754     PhabricatorFerretEngine $engine,
1755     PhabricatorSavedQuery $query) {
1756
1757     if (!$this->supportsFerretEngine()) {
1758       throw new Exception(
1759         pht(
1760           'Query ("%s") does not support the Ferret fulltext engine.',
1761           get_class($this)));
1762     }
1763
1764     $this->ferretEngine = $engine;
1765     $this->ferretQuery = $query;
1766
1767     return $this;
1768   }
1769
1770   public function getFerretTokens() {
1771     if (!$this->supportsFerretEngine()) {
1772       throw new Exception(
1773         pht(
1774           'Query ("%s") does not support the Ferret fulltext engine.',
1775           get_class($this)));
1776     }
1777
1778     return $this->ferretTokens;
1779   }
1780
1781   public function withFerretConstraint(
1782     PhabricatorFerretEngine $engine,
1783     array $fulltext_tokens) {
1784
1785     if (!$this->supportsFerretEngine()) {
1786       throw new Exception(
1787         pht(
1788           'Query ("%s") does not support the Ferret fulltext engine.',
1789           get_class($this)));
1790     }
1791
1792     if ($this->ferretEngine) {
1793       throw new Exception(
1794         pht(
1795           'Query may not have multiple fulltext constraints.'));
1796     }
1797
1798     if (!$fulltext_tokens) {
1799       return $this;
1800     }
1801
1802     $this->ferretEngine = $engine;
1803     $this->ferretTokens = $fulltext_tokens;
1804
1805     $op_absent = PhutilSearchQueryCompiler::OPERATOR_ABSENT;
1806
1807     $default_function = $engine->getDefaultFunctionKey();
1808     $table_map = array();
1809     $idx = 1;
1810     foreach ($this->ferretTokens as $fulltext_token) {
1811       $raw_token = $fulltext_token->getToken();
1812
1813       $function = $raw_token->getFunction();
1814       if ($function === null) {
1815         $function = $default_function;
1816       }
1817
1818       $function_def = $engine->getFunctionForName($function);
1819
1820       // NOTE: The query compiler guarantees that a query can not make a
1821       // field both "present" and "absent", so it's safe to just use the
1822       // first operator we encounter to determine whether the table is
1823       // optional or not.
1824
1825       $operator = $raw_token->getOperator();
1826       $is_optional = ($operator === $op_absent);
1827
1828       if (!isset($table_map[$function])) {
1829         $alias = 'ftfield_'.$idx++;
1830         $table_map[$function] = array(
1831           'alias' => $alias,
1832           'function' => $function_def,
1833           'optional' => $is_optional,
1834         );
1835       }
1836     }
1837
1838     // Join the title field separately so we can rank results.
1839     $table_map['rank'] = array(
1840       'alias' => 'ft_rank',
1841       'function' => $engine->getFunctionForName('title'),
1842
1843       // See T13345. Not every document has a title, so we want to LEFT JOIN
1844       // this table to avoid excluding documents with no title that match
1845       // the query in other fields.
1846       'optional' => true,
1847     );
1848
1849     $this->ferretTables = $table_map;
1850
1851     return $this;
1852   }
1853
1854   protected function buildFerretSelectClause(AphrontDatabaseConnection $conn) {
1855     $select = array();
1856
1857     if (!$this->supportsFerretEngine()) {
1858       return $select;
1859     }
1860
1861     if (!$this->hasFerretOrder()) {
1862       // We only need to SELECT the virtual rank/relevance columns if we're
1863       // actually sorting the results by rank.
1864       return $select;
1865     }
1866
1867     if (!$this->ferretEngine) {
1868       $select[] = qsprintf($conn, '0 AS %T', self::FULLTEXT_RANK);
1869       $select[] = qsprintf($conn, '0 AS %T', self::FULLTEXT_CREATED);
1870       $select[] = qsprintf($conn, '0 AS %T', self::FULLTEXT_MODIFIED);
1871       return $select;
1872     }
1873
1874     $engine = $this->ferretEngine;
1875     $stemmer = $engine->newStemmer();
1876
1877     $op_sub = PhutilSearchQueryCompiler::OPERATOR_SUBSTRING;
1878     $op_not = PhutilSearchQueryCompiler::OPERATOR_NOT;
1879     $table_alias = 'ft_rank';
1880
1881     $parts = array();
1882     foreach ($this->ferretTokens as $fulltext_token) {
1883       $raw_token = $fulltext_token->getToken();
1884       $value = $raw_token->getValue();
1885
1886       if ($raw_token->getOperator() == $op_not) {
1887         // Ignore "not" terms when ranking, since they aren't useful.
1888         continue;
1889       }
1890
1891       if ($raw_token->getOperator() == $op_sub) {
1892         $is_substring = true;
1893       } else {
1894         $is_substring = false;
1895       }
1896
1897       if ($is_substring) {
1898         $parts[] = qsprintf(
1899           $conn,
1900           'IF(%T.rawCorpus LIKE %~, 2, 0)',
1901           $table_alias,
1902           $value);
1903         continue;
1904       }
1905
1906       if ($raw_token->isQuoted()) {
1907         $is_quoted = true;
1908         $is_stemmed = false;
1909       } else {
1910         $is_quoted = false;
1911         $is_stemmed = true;
1912       }
1913
1914       $term_constraints = array();
1915
1916       $term_value = $engine->newTermsCorpus($value);
1917
1918       $parts[] = qsprintf(
1919         $conn,
1920         'IF(%T.termCorpus LIKE %~, 2, 0)',
1921         $table_alias,
1922         $term_value);
1923
1924       if ($is_stemmed) {
1925         $stem_value = $stemmer->stemToken($value);
1926         $stem_value = $engine->newTermsCorpus($stem_value);
1927
1928         $parts[] = qsprintf(
1929           $conn,
1930           'IF(%T.normalCorpus LIKE %~, 1, 0)',
1931           $table_alias,
1932           $stem_value);
1933       }
1934     }
1935
1936     $parts[] = qsprintf($conn, '%d', 0);
1937
1938     $sum = array_shift($parts);
1939     foreach ($parts as $part) {
1940       $sum = qsprintf(
1941         $conn,
1942         '%Q + %Q',
1943         $sum,
1944         $part);
1945     }
1946
1947     $select[] = qsprintf(
1948       $conn,
1949       '%Q AS %T',
1950       $sum,
1951       self::FULLTEXT_RANK);
1952
1953     // See D20297. We select these as real columns in the result set so that
1954     // constructions like this will work:
1955     //
1956     //   ((SELECT ...) UNION (SELECT ...)) ORDER BY ...
1957     //
1958     // If the columns aren't part of the result set, the final "ORDER BY" can
1959     // not act on them.
1960
1961     $select[] = qsprintf(
1962       $conn,
1963       'ft_doc.epochCreated AS %T',
1964       self::FULLTEXT_CREATED);
1965
1966     $select[] = qsprintf(
1967       $conn,
1968       'ft_doc.epochModified AS %T',
1969       self::FULLTEXT_MODIFIED);
1970
1971     return $select;
1972   }
1973
1974   protected function buildFerretJoinClause(AphrontDatabaseConnection $conn) {
1975     if (!$this->ferretEngine) {
1976       return array();
1977     }
1978
1979     $op_sub = PhutilSearchQueryCompiler::OPERATOR_SUBSTRING;
1980     $op_not = PhutilSearchQueryCompiler::OPERATOR_NOT;
1981     $op_absent = PhutilSearchQueryCompiler::OPERATOR_ABSENT;
1982     $op_present = PhutilSearchQueryCompiler::OPERATOR_PRESENT;
1983
1984     $engine = $this->ferretEngine;
1985     $stemmer = $engine->newStemmer();
1986
1987     $ngram_table = $engine->getNgramsTableName();
1988     $ngram_engine = $this->getNgramEngine();
1989
1990     $flat = array();
1991     foreach ($this->ferretTokens as $fulltext_token) {
1992       $raw_token = $fulltext_token->getToken();
1993
1994       $operator = $raw_token->getOperator();
1995
1996       // If this is a negated term like "-pomegranate", don't join the ngram
1997       // table since we aren't looking for documents with this term. (We could
1998       // LEFT JOIN the table and require a NULL row, but this is probably more
1999       // trouble than it's worth.)
2000       if ($operator === $op_not) {
2001         continue;
2002       }
2003
2004       // Neither the "present" or "absent" operators benefit from joining
2005       // the ngram table.
2006       if ($operator === $op_absent || $operator === $op_present) {
2007         continue;
2008       }
2009
2010       $value = $raw_token->getValue();
2011
2012       $length = count(phutil_utf8v($value));
2013
2014       if ($raw_token->getOperator() == $op_sub) {
2015         $is_substring = true;
2016       } else {
2017         $is_substring = false;
2018       }
2019
2020       // If the user specified a substring query for a substring which is
2021       // shorter than the ngram length, we can't use the ngram index, so
2022       // don't do a join. We'll fall back to just doing LIKE on the full
2023       // corpus.
2024       if ($is_substring) {
2025         if ($length < 3) {
2026           continue;
2027         }
2028       }
2029
2030       if ($raw_token->isQuoted()) {
2031         $is_stemmed = false;
2032       } else {
2033         $is_stemmed = true;
2034       }
2035
2036       if ($is_substring) {
2037         $ngrams = $ngram_engine->getSubstringNgramsFromString($value);
2038       } else {
2039         $terms_value = $engine->newTermsCorpus($value);
2040         $ngrams = $ngram_engine->getTermNgramsFromString($terms_value);
2041
2042         // If this is a stemmed term, only look for ngrams present in both the
2043         // unstemmed and stemmed variations.
2044         if ($is_stemmed) {
2045           // Trim the boundary space characters so the stemmer recognizes this
2046           // is (or, at least, may be) a normal word and activates.
2047           $terms_value = trim($terms_value, ' ');
2048           $stem_value = $stemmer->stemToken($terms_value);
2049           $stem_ngrams = $ngram_engine->getTermNgramsFromString($stem_value);
2050           $ngrams = array_intersect($ngrams, $stem_ngrams);
2051         }
2052       }
2053
2054       foreach ($ngrams as $ngram) {
2055         $flat[] = array(
2056           'table' => $ngram_table,
2057           'ngram' => $ngram,
2058         );
2059       }
2060     }
2061
2062     // Remove common ngrams, like "the", which occur too frequently in
2063     // documents to be useful in constraining the query. The best ngrams
2064     // are obscure sequences which occur in very few documents.
2065
2066     if ($flat) {
2067       $common_ngrams = queryfx_all(
2068         $conn,
2069         'SELECT ngram FROM %T WHERE ngram IN (%Ls)',
2070         $engine->getCommonNgramsTableName(),
2071         ipull($flat, 'ngram'));
2072       $common_ngrams = ipull($common_ngrams, 'ngram', 'ngram');
2073
2074       foreach ($flat as $key => $spec) {
2075         $ngram = $spec['ngram'];
2076         if (isset($common_ngrams[$ngram])) {
2077           unset($flat[$key]);
2078           continue;
2079         }
2080
2081         // NOTE: MySQL discards trailing whitespace in CHAR(X) columns.
2082         $trim_ngram = rtrim($ngram, ' ');
2083         if (isset($common_ngrams[$trim_ngram])) {
2084           unset($flat[$key]);
2085           continue;
2086         }
2087       }
2088     }
2089
2090     // MySQL only allows us to join a maximum of 61 tables per query. Each
2091     // ngram is going to cost us a join toward that limit, so if the user
2092     // specified a very long query string, just pick 16 of the ngrams
2093     // at random.
2094     if (count($flat) > 16) {
2095       shuffle($flat);
2096       $flat = array_slice($flat, 0, 16);
2097     }
2098
2099     $alias = $this->getPrimaryTableAlias();
2100     if ($alias) {
2101       $phid_column = qsprintf($conn, '%T.%T', $alias, 'phid');
2102     } else {
2103       $phid_column = qsprintf($conn, '%T', 'phid');
2104     }
2105
2106     $document_table = $engine->getDocumentTableName();
2107     $field_table = $engine->getFieldTableName();
2108
2109     $joins = array();
2110     $joins[] = qsprintf(
2111       $conn,
2112       'JOIN %T ft_doc ON ft_doc.objectPHID = %Q',
2113       $document_table,
2114       $phid_column);
2115
2116     $idx = 1;
2117     foreach ($flat as $spec) {
2118       $table = $spec['table'];
2119       $ngram = $spec['ngram'];
2120
2121       $alias = 'ftngram_'.$idx++;
2122
2123       $joins[] = qsprintf(
2124         $conn,
2125         'JOIN %T %T ON %T.documentID = ft_doc.id AND %T.ngram = %s',
2126         $table,
2127         $alias,
2128         $alias,
2129         $alias,
2130         $ngram);
2131     }
2132
2133     $object = $this->newResultObject();
2134     if (!$object) {
2135       throw new Exception(
2136         pht(
2137           'Query class ("%s") must define "newResultObject()" to use '.
2138           'Ferret constraints.',
2139           get_class($this)));
2140     }
2141
2142     // See T13511. If we have a fulltext query which uses valid field
2143     // functions, but at least one of the functions applies to a field which
2144     // the object can never have, the query can never match anything. Detect
2145     // this and return an empty result set.
2146
2147     // (Even if the query is "field is absent" or "field does not contain
2148     // such-and-such", the interpretation is that these constraints are
2149     // not meaningful when applied to an object which can never have the
2150     // field.)
2151
2152     $functions = ipull($this->ferretTables, 'function');
2153     $functions = mpull($functions, null, 'getFerretFunctionName');
2154     foreach ($functions as $function) {
2155       if (!$function->supportsObject($object)) {
2156         throw new PhabricatorEmptyQueryException(
2157           pht(
2158             'This query uses a fulltext function which this document '.
2159             'type does not support.'));
2160       }
2161     }
2162
2163     foreach ($this->ferretTables as $table) {
2164       $alias = $table['alias'];
2165
2166       if (empty($table['optional'])) {
2167         $join_type = qsprintf($conn, 'JOIN');
2168       } else {
2169         $join_type = qsprintf($conn, 'LEFT JOIN');
2170       }
2171
2172       $joins[] = qsprintf(
2173         $conn,
2174         '%Q %T %T ON ft_doc.id = %T.documentID
2175           AND %T.fieldKey = %s',
2176         $join_type,
2177         $field_table,
2178         $alias,
2179         $alias,
2180         $alias,
2181         $table['function']->getFerretFieldKey());
2182     }
2183
2184     return $joins;
2185   }
2186
2187   protected function buildFerretWhereClause(AphrontDatabaseConnection $conn) {
2188     if (!$this->ferretEngine) {
2189       return array();
2190     }
2191
2192     $engine = $this->ferretEngine;
2193     $stemmer = $engine->newStemmer();
2194     $table_map = $this->ferretTables;
2195
2196     $op_sub = PhutilSearchQueryCompiler::OPERATOR_SUBSTRING;
2197     $op_not = PhutilSearchQueryCompiler::OPERATOR_NOT;
2198     $op_exact = PhutilSearchQueryCompiler::OPERATOR_EXACT;
2199     $op_absent = PhutilSearchQueryCompiler::OPERATOR_ABSENT;
2200     $op_present = PhutilSearchQueryCompiler::OPERATOR_PRESENT;
2201
2202     $where = array();
2203     $default_function = $engine->getDefaultFunctionKey();
2204     foreach ($this->ferretTokens as $fulltext_token) {
2205       $raw_token = $fulltext_token->getToken();
2206       $value = $raw_token->getValue();
2207
2208       $function = $raw_token->getFunction();
2209       if ($function === null) {
2210         $function = $default_function;
2211       }
2212
2213       $operator = $raw_token->getOperator();
2214
2215       $table_alias = $table_map[$function]['alias'];
2216
2217       // If this is a "field is present" operator, we've already implicitly
2218       // guaranteed this by JOINing the table. We don't need to do any
2219       // more work.
2220       $is_present = ($operator === $op_present);
2221       if ($is_present) {
2222         continue;
2223       }
2224
2225       // If this is a "field is absent" operator, we just want documents
2226       // which failed to match to a row when we LEFT JOINed the table. This
2227       // means there's no index for the field.
2228       $is_absent = ($operator === $op_absent);
2229       if ($is_absent) {
2230         $where[] = qsprintf(
2231           $conn,
2232           '(%T.rawCorpus IS NULL)',
2233           $table_alias);
2234         continue;
2235       }
2236
2237       $is_not = ($operator === $op_not);
2238
2239       if ($operator == $op_sub) {
2240         $is_substring = true;
2241       } else {
2242         $is_substring = false;
2243       }
2244
2245       // If we're doing exact search, just test the raw corpus.
2246       $is_exact = ($operator === $op_exact);
2247       if ($is_exact) {
2248         if ($is_not) {
2249           $where[] = qsprintf(
2250             $conn,
2251             '(%T.rawCorpus != %s)',
2252             $table_alias,
2253             $value);
2254         } else {
2255           $where[] = qsprintf(
2256             $conn,
2257             '(%T.rawCorpus = %s)',
2258             $table_alias,
2259             $value);
2260         }
2261         continue;
2262       }
2263
2264       // If we're doing substring search, we just match against the raw corpus
2265       // and we're done.
2266       if ($is_substring) {
2267         if ($is_not) {
2268           $where[] = qsprintf(
2269             $conn,
2270             '(%T.rawCorpus NOT LIKE %~)',
2271             $table_alias,
2272             $value);
2273         } else {
2274           $where[] = qsprintf(
2275             $conn,
2276             '(%T.rawCorpus LIKE %~)',
2277             $table_alias,
2278             $value);
2279         }
2280         continue;
2281       }
2282
2283       // Otherwise, we need to match against the term corpus and the normal
2284       // corpus, so that searching for "raw" does not find "strawberry".
2285       if ($raw_token->isQuoted()) {
2286         $is_quoted = true;
2287         $is_stemmed = false;
2288       } else {
2289         $is_quoted = false;
2290         $is_stemmed = true;
2291       }
2292
2293       // Never stem negated queries, since this can exclude results users
2294       // did not mean to exclude and generally confuse things.
2295       if ($is_not) {
2296         $is_stemmed = false;
2297       }
2298
2299       $term_constraints = array();
2300
2301       $term_value = $engine->newTermsCorpus($value);
2302       if ($is_not) {
2303         $term_constraints[] = qsprintf(
2304           $conn,
2305           '(%T.termCorpus NOT LIKE %~)',
2306           $table_alias,
2307           $term_value);
2308       } else {
2309         $term_constraints[] = qsprintf(
2310           $conn,
2311           '(%T.termCorpus LIKE %~)',
2312           $table_alias,
2313           $term_value);
2314       }
2315
2316       if ($is_stemmed) {
2317         $stem_value = $stemmer->stemToken($value);
2318         $stem_value = $engine->newTermsCorpus($stem_value);
2319
2320         $term_constraints[] = qsprintf(
2321           $conn,
2322           '(%T.normalCorpus LIKE %~)',
2323           $table_alias,
2324           $stem_value);
2325       }
2326
2327       if ($is_not) {
2328         $where[] = qsprintf(
2329           $conn,
2330           '%LA',
2331           $term_constraints);
2332       } else if ($is_quoted) {
2333         $where[] = qsprintf(
2334           $conn,
2335           '(%T.rawCorpus LIKE %~ AND %LO)',
2336           $table_alias,
2337           $value,
2338           $term_constraints);
2339       } else {
2340         $where[] = qsprintf(
2341           $conn,
2342           '%LO',
2343           $term_constraints);
2344       }
2345     }
2346
2347     if ($this->ferretQuery) {
2348       $query = $this->ferretQuery;
2349
2350       $author_phids = $query->getParameter('authorPHIDs');
2351       if ($author_phids) {
2352         $where[] = qsprintf(
2353           $conn,
2354           'ft_doc.authorPHID IN (%Ls)',
2355           $author_phids);
2356       }
2357
2358       $with_unowned = $query->getParameter('withUnowned');
2359       $with_any = $query->getParameter('withAnyOwner');
2360
2361       if ($with_any && $with_unowned) {
2362         throw new PhabricatorEmptyQueryException(
2363           pht(
2364             'This query matches only unowned documents owned by anyone, '.
2365             'which is impossible.'));
2366       }
2367
2368       $owner_phids = $query->getParameter('ownerPHIDs');
2369       if ($owner_phids && !$with_any) {
2370         if ($with_unowned) {
2371           $where[] = qsprintf(
2372             $conn,
2373             'ft_doc.ownerPHID IN (%Ls) OR ft_doc.ownerPHID IS NULL',
2374             $owner_phids);
2375         } else {
2376           $where[] = qsprintf(
2377             $conn,
2378             'ft_doc.ownerPHID IN (%Ls)',
2379             $owner_phids);
2380         }
2381       } else if ($with_unowned) {
2382         $where[] = qsprintf(
2383           $conn,
2384           'ft_doc.ownerPHID IS NULL');
2385       }
2386
2387       if ($with_any) {
2388         $where[] = qsprintf(
2389           $conn,
2390           'ft_doc.ownerPHID IS NOT NULL');
2391       }
2392
2393       $rel_open = PhabricatorSearchRelationship::RELATIONSHIP_OPEN;
2394
2395       $statuses = $query->getParameter('statuses');
2396       $is_closed = null;
2397       if ($statuses) {
2398         $statuses = array_fuse($statuses);
2399         if (count($statuses) == 1) {
2400           if (isset($statuses[$rel_open])) {
2401             $is_closed = 0;
2402           } else {
2403             $is_closed = 1;
2404           }
2405         }
2406       }
2407
2408       if ($is_closed !== null) {
2409         $where[] = qsprintf(
2410           $conn,
2411           'ft_doc.isClosed = %d',
2412           $is_closed);
2413       }
2414     }
2415
2416     return $where;
2417   }
2418
2419   protected function shouldGroupFerretResultRows() {
2420     return (bool)$this->ferretTokens;
2421   }
2422
2423
2424 /* -(  Ngrams  )------------------------------------------------------------- */
2425
2426
2427   protected function withNgramsConstraint(
2428     PhabricatorSearchNgrams $index,
2429     $value) {
2430
2431     if (strlen($value)) {
2432       $this->ngrams[] = array(
2433         'index' => $index,
2434         'value' => $value,
2435         'length' => count(phutil_utf8v($value)),
2436       );
2437     }
2438
2439     return $this;
2440   }
2441
2442
2443   protected function buildNgramsJoinClause(AphrontDatabaseConnection $conn) {
2444     $ngram_engine = $this->getNgramEngine();
2445
2446     $flat = array();
2447     foreach ($this->ngrams as $spec) {
2448       $length = $spec['length'];
2449
2450       if ($length < 3) {
2451         continue;
2452       }
2453
2454       $index = $spec['index'];
2455       $value = $spec['value'];
2456
2457       $ngrams = $ngram_engine->getSubstringNgramsFromString($value);
2458
2459       foreach ($ngrams as $ngram) {
2460         $flat[] = array(
2461           'table' => $index->getTableName(),
2462           'ngram' => $ngram,
2463         );
2464       }
2465     }
2466
2467     if (!$flat) {
2468       return array();
2469     }
2470
2471     // MySQL only allows us to join a maximum of 61 tables per query. Each
2472     // ngram is going to cost us a join toward that limit, so if the user
2473     // specified a very long query string, just pick 16 of the ngrams
2474     // at random.
2475     if (count($flat) > 16) {
2476       shuffle($flat);
2477       $flat = array_slice($flat, 0, 16);
2478     }
2479
2480     $alias = $this->getPrimaryTableAlias();
2481     if ($alias) {
2482       $id_column = qsprintf($conn, '%T.%T', $alias, 'id');
2483     } else {
2484       $id_column = qsprintf($conn, '%T', 'id');
2485     }
2486
2487     $idx = 1;
2488     $joins = array();
2489     foreach ($flat as $spec) {
2490       $table = $spec['table'];
2491       $ngram = $spec['ngram'];
2492
2493       $alias = 'ngm'.$idx++;
2494
2495       $joins[] = qsprintf(
2496         $conn,
2497         'JOIN %T %T ON %T.objectID = %Q AND %T.ngram = %s',
2498         $table,
2499         $alias,
2500         $alias,
2501         $id_column,
2502         $alias,
2503         $ngram);
2504     }
2505
2506     return $joins;
2507   }
2508
2509
2510   protected function buildNgramsWhereClause(AphrontDatabaseConnection $conn) {
2511     $where = array();
2512
2513     $ngram_engine = $this->getNgramEngine();
2514
2515     foreach ($this->ngrams as $ngram) {
2516       $index = $ngram['index'];
2517       $value = $ngram['value'];
2518
2519       $column = $index->getColumnName();
2520       $alias = $this->getPrimaryTableAlias();
2521       if ($alias) {
2522         $column = qsprintf($conn, '%T.%T', $alias, $column);
2523       } else {
2524         $column = qsprintf($conn, '%T', $column);
2525       }
2526
2527       $tokens = $ngram_engine->tokenizeNgramString($value);
2528
2529       foreach ($tokens as $token) {
2530         $where[] = qsprintf(
2531           $conn,
2532           '%Q LIKE %~',
2533           $column,
2534           $token);
2535       }
2536     }
2537
2538     return $where;
2539   }
2540
2541
2542   protected function shouldGroupNgramResultRows() {
2543     return (bool)$this->ngrams;
2544   }
2545
2546   private function getNgramEngine() {
2547     if (!$this->ngramEngine) {
2548       $this->ngramEngine = new PhabricatorSearchNgramEngine();
2549     }
2550
2551     return $this->ngramEngine;
2552   }
2553
2554
2555 /* -(  Edge Logic  )--------------------------------------------------------- */
2556
2557
2558   /**
2559    * Convenience method for specifying edge logic constraints with a list of
2560    * PHIDs.
2561    *
2562    * @param const Edge constant.
2563    * @param const Constraint operator.
2564    * @param list<phid> List of PHIDs.
2565    * @return this
2566    * @task edgelogic
2567    */
2568   public function withEdgeLogicPHIDs($edge_type, $operator, array $phids) {
2569     $constraints = array();
2570     foreach ($phids as $phid) {
2571       $constraints[] = new PhabricatorQueryConstraint($operator, $phid);
2572     }
2573
2574     return $this->withEdgeLogicConstraints($edge_type, $constraints);
2575   }
2576
2577
2578   /**
2579    * @return this
2580    * @task edgelogic
2581    */
2582   public function withEdgeLogicConstraints($edge_type, array $constraints) {
2583     assert_instances_of($constraints, 'PhabricatorQueryConstraint');
2584
2585     $constraints = mgroup($constraints, 'getOperator');
2586     foreach ($constraints as $operator => $list) {
2587       foreach ($list as $item) {
2588         $this->edgeLogicConstraints[$edge_type][$operator][] = $item;
2589       }
2590     }
2591
2592     $this->edgeLogicConstraintsAreValid = false;
2593
2594     return $this;
2595   }
2596
2597
2598   /**
2599    * @task edgelogic
2600    */
2601   public function buildEdgeLogicSelectClause(AphrontDatabaseConnection $conn) {
2602     $select = array();
2603
2604     $this->validateEdgeLogicConstraints();
2605
2606     foreach ($this->edgeLogicConstraints as $type => $constraints) {
2607       foreach ($constraints as $operator => $list) {
2608         $alias = $this->getEdgeLogicTableAlias($operator, $type);
2609         switch ($operator) {
2610           case PhabricatorQueryConstraint::OPERATOR_AND:
2611             if (count($list) > 1) {
2612               $select[] = qsprintf(
2613                 $conn,
2614                 'COUNT(DISTINCT(%T.dst)) %T',
2615                 $alias,
2616                 $this->buildEdgeLogicTableAliasCount($alias));
2617             }
2618             break;
2619           case PhabricatorQueryConstraint::OPERATOR_ANCESTOR:
2620             // This is tricky. We have a query which specifies multiple
2621             // projects, each of which may have an arbitrarily large number
2622             // of descendants.
2623
2624             // Suppose the projects are "Engineering" and "Operations", and
2625             // "Engineering" has subprojects X, Y and Z.
2626
2627             // We first use `FIELD(dst, X, Y, Z)` to produce a 0 if a row
2628             // is not part of Engineering at all, or some number other than
2629             // 0 if it is.
2630
2631             // Then we use `IF(..., idx, NULL)` to convert the 0 to a NULL and
2632             // any other value to an index (say, 1) for the ancestor.
2633
2634             // We build these up for every ancestor, then use `COALESCE(...)`
2635             // to select the non-null one, giving us an ancestor which this
2636             // row is a member of.
2637
2638             // From there, we use `COUNT(DISTINCT(...))` to make sure that
2639             // each result row is a member of all ancestors.
2640             if (count($list) > 1) {
2641               $idx = 1;
2642               $parts = array();
2643               foreach ($list as $constraint) {
2644                 $parts[] = qsprintf(
2645                   $conn,
2646                   'IF(FIELD(%T.dst, %Ls) != 0, %d, NULL)',
2647                   $alias,
2648                   (array)$constraint->getValue(),
2649                   $idx++);
2650               }
2651               $parts = qsprintf($conn, '%LQ', $parts);
2652
2653               $select[] = qsprintf(
2654                 $conn,
2655                 'COUNT(DISTINCT(COALESCE(%Q))) %T',
2656                 $parts,
2657                 $this->buildEdgeLogicTableAliasAncestor($alias));
2658             }
2659             break;
2660           default:
2661             break;
2662         }
2663       }
2664     }
2665
2666     return $select;
2667   }
2668
2669
2670   /**
2671    * @task edgelogic
2672    */
2673   public function buildEdgeLogicJoinClause(AphrontDatabaseConnection $conn) {
2674     $edge_table = PhabricatorEdgeConfig::TABLE_NAME_EDGE;
2675     $phid_column = $this->getApplicationSearchObjectPHIDColumn($conn);
2676
2677     $joins = array();
2678     foreach ($this->edgeLogicConstraints as $type => $constraints) {
2679
2680       $op_null = PhabricatorQueryConstraint::OPERATOR_NULL;
2681       $has_null = isset($constraints[$op_null]);
2682
2683       // If we're going to process an only() operator, build a list of the
2684       // acceptable set of PHIDs first. We'll only match results which have
2685       // no edges to any other PHIDs.
2686       $all_phids = array();
2687       if (isset($constraints[PhabricatorQueryConstraint::OPERATOR_ONLY])) {
2688         foreach ($constraints as $operator => $list) {
2689           switch ($operator) {
2690             case PhabricatorQueryConstraint::OPERATOR_ANCESTOR:
2691             case PhabricatorQueryConstraint::OPERATOR_AND:
2692             case PhabricatorQueryConstraint::OPERATOR_OR:
2693               foreach ($list as $constraint) {
2694                 $value = (array)$constraint->getValue();
2695                 foreach ($value as $v) {
2696                   $all_phids[$v] = $v;
2697                 }
2698               }
2699               break;
2700           }
2701         }
2702       }
2703
2704       foreach ($constraints as $operator => $list) {
2705         $alias = $this->getEdgeLogicTableAlias($operator, $type);
2706
2707         $phids = array();
2708         foreach ($list as $constraint) {
2709           $value = (array)$constraint->getValue();
2710           foreach ($value as $v) {
2711             $phids[$v] = $v;
2712           }
2713         }
2714         $phids = array_keys($phids);
2715
2716         switch ($operator) {
2717           case PhabricatorQueryConstraint::OPERATOR_NOT:
2718             $joins[] = qsprintf(
2719               $conn,
2720               'LEFT JOIN %T %T ON %Q = %T.src AND %T.type = %d
2721                 AND %T.dst IN (%Ls)',
2722               $edge_table,
2723               $alias,
2724               $phid_column,
2725               $alias,
2726               $alias,
2727               $type,
2728               $alias,
2729               $phids);
2730             break;
2731           case PhabricatorQueryConstraint::OPERATOR_ANCESTOR:
2732           case PhabricatorQueryConstraint::OPERATOR_AND:
2733           case PhabricatorQueryConstraint::OPERATOR_OR:
2734             // If we're including results with no matches, we have to degrade
2735             // this to a LEFT join. We'll use WHERE to select matching rows
2736             // later.
2737             if ($has_null) {
2738               $join_type = qsprintf($conn, 'LEFT');
2739             } else {
2740               $join_type = qsprintf($conn, '');
2741             }
2742
2743             $joins[] = qsprintf(
2744               $conn,
2745               '%Q JOIN %T %T ON %Q = %T.src AND %T.type = %d
2746                 AND %T.dst IN (%Ls)',
2747               $join_type,
2748               $edge_table,
2749               $alias,
2750               $phid_column,
2751               $alias,
2752               $alias,
2753               $type,
2754               $alias,
2755               $phids);
2756             break;
2757           case PhabricatorQueryConstraint::OPERATOR_NULL:
2758             $joins[] = qsprintf(
2759               $conn,
2760               'LEFT JOIN %T %T ON %Q = %T.src AND %T.type = %d',
2761               $edge_table,
2762               $alias,
2763               $phid_column,
2764               $alias,
2765               $alias,
2766               $type);
2767             break;
2768           case PhabricatorQueryConstraint::OPERATOR_ONLY:
2769             $joins[] = qsprintf(
2770               $conn,
2771               'LEFT JOIN %T %T ON %Q = %T.src AND %T.type = %d
2772                 AND %T.dst NOT IN (%Ls)',
2773               $edge_table,
2774               $alias,
2775               $phid_column,
2776               $alias,
2777               $alias,
2778               $type,
2779               $alias,
2780               $all_phids);
2781             break;
2782         }
2783       }
2784     }
2785
2786     return $joins;
2787   }
2788
2789
2790   /**
2791    * @task edgelogic
2792    */
2793   public function buildEdgeLogicWhereClause(AphrontDatabaseConnection $conn) {
2794     $where = array();
2795
2796     foreach ($this->edgeLogicConstraints as $type => $constraints) {
2797
2798       $full = array();
2799       $null = array();
2800
2801       $op_null = PhabricatorQueryConstraint::OPERATOR_NULL;
2802       $has_null = isset($constraints[$op_null]);
2803
2804       foreach ($constraints as $operator => $list) {
2805         $alias = $this->getEdgeLogicTableAlias($operator, $type);
2806         switch ($operator) {
2807           case PhabricatorQueryConstraint::OPERATOR_NOT:
2808           case PhabricatorQueryConstraint::OPERATOR_ONLY:
2809             $full[] = qsprintf(
2810               $conn,
2811               '%T.dst IS NULL',
2812               $alias);
2813             break;
2814           case PhabricatorQueryConstraint::OPERATOR_AND:
2815           case PhabricatorQueryConstraint::OPERATOR_OR:
2816             if ($has_null) {
2817               $full[] = qsprintf(
2818                 $conn,
2819                 '%T.dst IS NOT NULL',
2820                 $alias);
2821             }
2822             break;
2823           case PhabricatorQueryConstraint::OPERATOR_NULL:
2824             $null[] = qsprintf(
2825               $conn,
2826               '%T.dst IS NULL',
2827               $alias);
2828             break;
2829         }
2830       }
2831
2832       if ($full && $null) {
2833         $where[] = qsprintf($conn, '(%LA OR %LA)', $full, $null);
2834       } else if ($full) {
2835         foreach ($full as $condition) {
2836           $where[] = $condition;
2837         }
2838       } else if ($null) {
2839         foreach ($null as $condition) {
2840           $where[] = $condition;
2841         }
2842       }
2843     }
2844
2845     return $where;
2846   }
2847
2848
2849   /**
2850    * @task edgelogic
2851    */
2852   public function buildEdgeLogicHavingClause(AphrontDatabaseConnection $conn) {
2853     $having = array();
2854
2855     foreach ($this->edgeLogicConstraints as $type => $constraints) {
2856       foreach ($constraints as $operator => $list) {
2857         $alias = $this->getEdgeLogicTableAlias($operator, $type);
2858         switch ($operator) {
2859           case PhabricatorQueryConstraint::OPERATOR_AND:
2860             if (count($list) > 1) {
2861               $having[] = qsprintf(
2862                 $conn,
2863                 '%T = %d',
2864                 $this->buildEdgeLogicTableAliasCount($alias),
2865                 count($list));
2866             }
2867             break;
2868           case PhabricatorQueryConstraint::OPERATOR_ANCESTOR:
2869             if (count($list) > 1) {
2870               $having[] = qsprintf(
2871                 $conn,
2872                 '%T = %d',
2873                 $this->buildEdgeLogicTableAliasAncestor($alias),
2874                 count($list));
2875             }
2876             break;
2877         }
2878       }
2879     }
2880
2881     return $having;
2882   }
2883
2884
2885   /**
2886    * @task edgelogic
2887    */
2888   public function shouldGroupEdgeLogicResultRows() {
2889     foreach ($this->edgeLogicConstraints as $type => $constraints) {
2890       foreach ($constraints as $operator => $list) {
2891         switch ($operator) {
2892           case PhabricatorQueryConstraint::OPERATOR_NOT:
2893           case PhabricatorQueryConstraint::OPERATOR_AND:
2894           case PhabricatorQueryConstraint::OPERATOR_OR:
2895             if (count($list) > 1) {
2896               return true;
2897             }
2898             break;
2899           case PhabricatorQueryConstraint::OPERATOR_ANCESTOR:
2900             // NOTE: We must always group query results rows when using an
2901             // "ANCESTOR" operator because a single task may be related to
2902             // two different descendants of a particular ancestor. For
2903             // discussion, see T12753.
2904             return true;
2905           case PhabricatorQueryConstraint::OPERATOR_NULL:
2906           case PhabricatorQueryConstraint::OPERATOR_ONLY:
2907             return true;
2908         }
2909       }
2910     }
2911
2912     return false;
2913   }
2914
2915
2916   /**
2917    * @task edgelogic
2918    */
2919   private function getEdgeLogicTableAlias($operator, $type) {
2920     return 'edgelogic_'.$operator.'_'.$type;
2921   }
2922
2923
2924   /**
2925    * @task edgelogic
2926    */
2927   private function buildEdgeLogicTableAliasCount($alias) {
2928     return $alias.'_count';
2929   }
2930
2931   /**
2932    * @task edgelogic
2933    */
2934   private function buildEdgeLogicTableAliasAncestor($alias) {
2935     return $alias.'_ancestor';
2936   }
2937
2938
2939   /**
2940    * Select certain edge logic constraint values.
2941    *
2942    * @task edgelogic
2943    */
2944   protected function getEdgeLogicValues(
2945     array $edge_types,
2946     array $operators) {
2947
2948     $values = array();
2949
2950     $constraint_lists = $this->edgeLogicConstraints;
2951     if ($edge_types) {
2952       $constraint_lists = array_select_keys($constraint_lists, $edge_types);
2953     }
2954
2955     foreach ($constraint_lists as $type => $constraints) {
2956       if ($operators) {
2957         $constraints = array_select_keys($constraints, $operators);
2958       }
2959       foreach ($constraints as $operator => $list) {
2960         foreach ($list as $constraint) {
2961           $value = (array)$constraint->getValue();
2962           foreach ($value as $v) {
2963             $values[] = $v;
2964           }
2965         }
2966       }
2967     }
2968
2969     return $values;
2970   }
2971
2972
2973   /**
2974    * Validate edge logic constraints for the query.
2975    *
2976    * @return this
2977    * @task edgelogic
2978    */
2979   private function validateEdgeLogicConstraints() {
2980     if ($this->edgeLogicConstraintsAreValid) {
2981       return $this;
2982     }
2983
2984     foreach ($this->edgeLogicConstraints as $type => $constraints) {
2985       foreach ($constraints as $operator => $list) {
2986         switch ($operator) {
2987           case PhabricatorQueryConstraint::OPERATOR_EMPTY:
2988             throw new PhabricatorEmptyQueryException(
2989               pht('This query specifies an empty constraint.'));
2990         }
2991       }
2992     }
2993
2994     // This should probably be more modular, eventually, but we only do
2995     // project-based edge logic today.
2996
2997     $project_phids = $this->getEdgeLogicValues(
2998       array(
2999         PhabricatorProjectObjectHasProjectEdgeType::EDGECONST,
3000       ),
3001       array(
3002         PhabricatorQueryConstraint::OPERATOR_AND,
3003         PhabricatorQueryConstraint::OPERATOR_OR,
3004         PhabricatorQueryConstraint::OPERATOR_NOT,
3005         PhabricatorQueryConstraint::OPERATOR_ANCESTOR,
3006       ));
3007     if ($project_phids) {
3008       $projects = id(new PhabricatorProjectQuery())
3009         ->setViewer($this->getViewer())
3010         ->setParentQuery($this)
3011         ->withPHIDs($project_phids)
3012         ->execute();
3013       $projects = mpull($projects, null, 'getPHID');
3014       foreach ($project_phids as $phid) {
3015         if (empty($projects[$phid])) {
3016           throw new PhabricatorEmptyQueryException(
3017             pht(
3018               'This query is constrained by a project you do not have '.
3019               'permission to see.'));
3020         }
3021       }
3022     }
3023
3024     $op_and = PhabricatorQueryConstraint::OPERATOR_AND;
3025     $op_or = PhabricatorQueryConstraint::OPERATOR_OR;
3026     $op_ancestor = PhabricatorQueryConstraint::OPERATOR_ANCESTOR;
3027
3028     foreach ($this->edgeLogicConstraints as $type => $constraints) {
3029       foreach ($constraints as $operator => $list) {
3030         switch ($operator) {
3031           case PhabricatorQueryConstraint::OPERATOR_ONLY:
3032             if (count($list) > 1) {
3033               throw new PhabricatorEmptyQueryException(
3034                 pht(
3035                   'This query specifies only() more than once.'));
3036             }
3037
3038             $have_and = idx($constraints, $op_and);
3039             $have_or = idx($constraints, $op_or);
3040             $have_ancestor = idx($constraints, $op_ancestor);
3041             if (!$have_and && !$have_or && !$have_ancestor) {
3042               throw new PhabricatorEmptyQueryException(
3043                 pht(
3044                   'This query specifies only(), but no other constraints '.
3045                   'which it can apply to.'));
3046             }
3047             break;
3048         }
3049       }
3050     }
3051
3052     $this->edgeLogicConstraintsAreValid = true;
3053
3054     return $this;
3055   }
3056
3057
3058 /* -(  Spaces  )------------------------------------------------------------- */
3059
3060
3061   /**
3062    * Constrain the query to return results from only specific Spaces.
3063    *
3064    * Pass a list of Space PHIDs, or `null` to represent the default space. Only
3065    * results in those Spaces will be returned.
3066    *
3067    * Queries are always constrained to include only results from spaces the
3068    * viewer has access to.
3069    *
3070    * @param list<phid|null>
3071    * @task spaces
3072    */
3073   public function withSpacePHIDs(array $space_phids) {
3074     $object = $this->newResultObject();
3075
3076     if (!$object) {
3077       throw new Exception(
3078         pht(
3079           'This query (of class "%s") does not implement newResultObject(), '.
3080           'but must implement this method to enable support for Spaces.',
3081           get_class($this)));
3082     }
3083
3084     if (!($object instanceof PhabricatorSpacesInterface)) {
3085       throw new Exception(
3086         pht(
3087           'This query (of class "%s") returned an object of class "%s" from '.
3088           'getNewResultObject(), but it does not implement the required '.
3089           'interface ("%s"). Objects must implement this interface to enable '.
3090           'Spaces support.',
3091           get_class($this),
3092           get_class($object),
3093           'PhabricatorSpacesInterface'));
3094     }
3095
3096     $this->spacePHIDs = $space_phids;
3097
3098     return $this;
3099   }
3100
3101   public function withSpaceIsArchived($archived) {
3102     $this->spaceIsArchived = $archived;
3103     return $this;
3104   }
3105
3106
3107   /**
3108    * Constrain the query to include only results in valid Spaces.
3109    *
3110    * This method builds part of a WHERE clause which considers the spaces the
3111    * viewer has access to see with any explicit constraint on spaces added by
3112    * @{method:withSpacePHIDs}.
3113    *
3114    * @param AphrontDatabaseConnection Database connection.
3115    * @return string Part of a WHERE clause.
3116    * @task spaces
3117    */
3118   private function buildSpacesWhereClause(AphrontDatabaseConnection $conn) {
3119     $object = $this->newResultObject();
3120     if (!$object) {
3121       return null;
3122     }
3123
3124     if (!($object instanceof PhabricatorSpacesInterface)) {
3125       return null;
3126     }
3127
3128     $viewer = $this->getViewer();
3129
3130     // If we have an omnipotent viewer and no formal space constraints, don't
3131     // emit a clause. This primarily enables older migrations to run cleanly,
3132     // without fataling because they try to match a `spacePHID` column which
3133     // does not exist yet. See T8743, T8746.
3134     if ($viewer->isOmnipotent()) {
3135       if ($this->spaceIsArchived === null && $this->spacePHIDs === null) {
3136         return null;
3137       }
3138     }
3139
3140     // See T13240. If this query raises policy exceptions, don't filter objects
3141     // in the MySQL layer. We want them to reach the application layer so we
3142     // can reject them and raise an exception.
3143     if ($this->shouldRaisePolicyExceptions()) {
3144       return null;
3145     }
3146
3147     $space_phids = array();
3148     $include_null = false;
3149
3150     $all = PhabricatorSpacesNamespaceQuery::getAllSpaces();
3151     if (!$all) {
3152       // If there are no spaces at all, implicitly give the viewer access to
3153       // the default space.
3154       $include_null = true;
3155     } else {
3156       // Otherwise, give them access to the spaces they have permission to
3157       // see.
3158       $viewer_spaces = PhabricatorSpacesNamespaceQuery::getViewerSpaces(
3159         $viewer);
3160       foreach ($viewer_spaces as $viewer_space) {
3161         if ($this->spaceIsArchived !== null) {
3162           if ($viewer_space->getIsArchived() != $this->spaceIsArchived) {
3163             continue;
3164           }
3165         }
3166         $phid = $viewer_space->getPHID();
3167         $space_phids[$phid] = $phid;
3168         if ($viewer_space->getIsDefaultNamespace()) {
3169           $include_null = true;
3170         }
3171       }
3172     }
3173
3174     // If we have additional explicit constraints, evaluate them now.
3175     if ($this->spacePHIDs !== null) {
3176       $explicit = array();
3177       $explicit_null = false;
3178       foreach ($this->spacePHIDs as $phid) {
3179         if ($phid === null) {
3180           $space = PhabricatorSpacesNamespaceQuery::getDefaultSpace();
3181         } else {
3182           $space = idx($all, $phid);
3183         }
3184
3185         if ($space) {
3186           $phid = $space->getPHID();
3187           $explicit[$phid] = $phid;
3188           if ($space->getIsDefaultNamespace()) {
3189             $explicit_null = true;
3190           }
3191         }
3192       }
3193
3194       // If the viewer can see the default space but it isn't on the explicit
3195       // list of spaces to query, don't match it.
3196       if ($include_null && !$explicit_null) {
3197         $include_null = false;
3198       }
3199
3200       // Include only the spaces common to the viewer and the constraints.
3201       $space_phids = array_intersect_key($space_phids, $explicit);
3202     }
3203
3204     if (!$space_phids && !$include_null) {
3205       if ($this->spacePHIDs === null) {
3206         throw new PhabricatorEmptyQueryException(
3207           pht('You do not have access to any spaces.'));
3208       } else {
3209         throw new PhabricatorEmptyQueryException(
3210           pht(
3211             'You do not have access to any of the spaces this query '.
3212             'is constrained to.'));
3213       }
3214     }
3215
3216     $alias = $this->getPrimaryTableAlias();
3217     if ($alias) {
3218       $col = qsprintf($conn, '%T.spacePHID', $alias);
3219     } else {
3220       $col = qsprintf($conn, 'spacePHID');
3221     }
3222
3223     if ($space_phids && $include_null) {
3224       return qsprintf(
3225         $conn,
3226         '(%Q IN (%Ls) OR %Q IS NULL)',
3227         $col,
3228         $space_phids,
3229         $col);
3230     } else if ($space_phids) {
3231       return qsprintf(
3232         $conn,
3233         '%Q IN (%Ls)',
3234         $col,
3235         $space_phids);
3236     } else {
3237       return qsprintf(
3238         $conn,
3239         '%Q IS NULL',
3240         $col);
3241     }
3242   }
3243
3244   private function hasFerretOrder() {
3245     $vector = $this->getOrderVector();
3246
3247     if ($vector->containsKey('rank')) {
3248       return true;
3249     }
3250
3251     if ($vector->containsKey('fulltext-created')) {
3252       return true;
3253     }
3254
3255     if ($vector->containsKey('fulltext-modified')) {
3256       return true;
3257     }
3258
3259     return false;
3260   }
3261
3262 }