[mlir][sparse] Moving the sort from factory method to the constructor.

[wrengr]

Summary

This guarantees the preconditions of fromCOO; whereas prior to this, one could call the constructor directly with an unsorted tensor, which would cause fromCOO to misbehave.

[aartbik]

At one point the idea was the perhaps some paths do not need a sort, since it is already sorted at construction time.
In the long run, perhaps we should add a "isSorted" field to the tensor and skip sorting when already done.

mlir/lib/ExecutionEngine/SparseTensorUtils.cpp

274

sort lexicographically

[wrengr]

addressing comments

mlir/lib/ExecutionEngine/SparseTensorUtils.cpp

274

I fleshed out the comment a bit more, but imo it's redundant to say lexicographic since that's always what SparseTensorCOO::sort does. If we really need that to be explicit everywhere, then we should rename the method to lexicographicSort

[aartbik]

mlir/lib/ExecutionEngine/SparseTensorUtils.cpp

274

It was more that the originally comment was dropped. The new version seems way to verbose, how about going back to the original:

// We sort the tensor lexicographically here, to ensure the preconditions for `fromCOO`.

[wrengr]

addressing nits

mlir/lib/ExecutionEngine/SparseTensorUtils.cpp

void add(const std::vector<uint64_t> &ind, V val) {
     assert(rank == ind.size());
     for (uint64_t r = 0; r < rank; r++)
       assert(ind[r] < sizes[r]); // within bounds
     elements.emplace_back(ind, val);
   }
   /// Sorts elements lexicographically by index.
   void sort() {
     assert(!iteratorLocked && "Attempt to sort() after startIterator()");
+    // TODO: we may want to cache an `isSorted` bit, to avoid
+    // unnecessary/redundant sorting.
     std::sort(elements.begin(), elements.end(), lexOrder);
   }
   /// Returns rank.
   uint64_t getRank() const { return sizes.size(); }
   /// Getter for sizes array.
   const std::vector<uint64_t> &getSizes() const { return sizes; }
   /// Getter for elements array.
   const std::vector<Element<V>> &getElements() const { return elements; }
for (uint64_t r = 0; r < rank; r++) {
       }
     }
     // Prepare sparse pointer structures for all dimensions.
     for (uint64_t r = 0; r < rank; r++)
       if (sparsity[r] == DimLevelType::kCompressed)
         pointers[r].push_back(0);
     // Then assign contents from coordinate scheme tensor if provided.
     if (tensor) {
+      // Lexicographically sort the tensor, to ensure precondition of `fromCOO`.
+      tensor->sort();
       const std::vector<Element<V>> &elements = tensor->getElements();
       uint64_t nnz = elements.size();
       values.reserve(nnz);
       fromCOO(elements, 0, nnz, 0);
     } else if (allDense) {
       values.resize(sz, 0);
     }
   }
public:
   static SparseTensorStorage<P, I, V> *
   newSparseTensor(uint64_t rank, const uint64_t *sizes, const uint64_t *perm,
                   const DimLevelType *sparsity, SparseTensorCOO<V> *tensor) {
     SparseTensorStorage<P, I, V> *n = nullptr;
     if (tensor) {
       assert(tensor->getRank() == rank);
       for (uint64_t r = 0; r < rank; r++)
         assert(sizes[r] == 0 || tensor->getSizes()[perm[r]] == sizes[r]);
-      tensor->sort(); // sort lexicographically
       n = new SparseTensorStorage<P, I, V>(tensor->getSizes(), perm, sparsity,
                                            tensor);
       delete tensor;
     } else {
       std::vector<uint64_t> permsz(rank);
       for (uint64_t r = 0; r < rank; r++)
         permsz[perm[r]] = sizes[r];
       n = new SparseTensorStorage<P, I, V>(permsz, perm, sparsity);
     }
     return n;
   }
 
 private:
   /// Initializes sparse tensor storage scheme from a memory-resident sparse
   /// tensor in coordinate scheme. This method prepares the pointers and
   /// indices arrays under the given per-dimension dense/sparse annotations.
+  /// Precondition: the `elements` must be lexicographically sorted.
   void fromCOO(const std::vector<Element<V>> &elements, uint64_t lo,
                uint64_t hi, uint64_t d) {
     // Once dimensions are exhausted, insert the numerical values.
     assert(d <= getRank());
     if (d == getRank()) {
       assert(lo < hi && hi <= elements.size());
       values.push_back(elements[lo].value);
       return;