Disallow duplicates in array

Question

I have 2-dimentional array of enum values initialized by constsnt values. I want to specify type of this array in such way, that it's not allowed to place same value more than once anywhere in the array. Note that I don't need each value to be used.

How can I do it?

Example:

const enum Smth {
  a = "a",
  b = "b",
  c = "c",
  d = "d",
}

type Unique2dArray<T> = T[][] // Want to write this type

const x: Unique2dArray<Smth> = [ // Should be valid
  [Smth.a, Smth.b],
  [Smth.d],
]

const y: Unique2dArray<Smth> = [ // Should NOT be valid (Smth.a is repeated)
  [Smth.a, Smth.b, Smth.a],
  [Smth.d],
]

const z: Unique2dArray<Smth> = [ // Should NOT be valid (Smth.a is repeated)
  [Smth.a, Smth.b],
  [Smth.d, Smth.a],
]

Do you need a compile-time-, or a runtime check? Also, what have you tried already? — Caramiriel, Nov 25 '19 at 13:27
@Caramiriel, compile-time. I don't have good ideas how I can do that. I can easely write runtime check, but I don't want it to be runtime as everything is explicitely writen in code. — Qwertiy, Nov 25 '19 at 13:29
Possible duplicate of [Is there a way to define type for array with unique items in typescript?](https://stackoverflow.com/questions/57016728/is-there-a-way-to-define-type-for-array-with-unique-items-in-typescript) — jcalz, Nov 25 '19 at 14:05

score 1 · Accepted Answer · answered Nov 25 '19 at 14:55

I'm giving this an answer because the 2d nature of it is a bit more complicated. It's basically the same technique as in the answer to this question:

Comments inline:

// BlankOut2D<T, K, L> takes a nested tuple T, and a pair of indices, and
// replaces the value in the tuple with never.
// So BlankOut2D<[['a','b'],['c','d']],'0','1'> is [['a',never],['c','d']].
type BlankOut2D<T extends ReadonlyArray<ReadonlyArray<any>>, K extends keyof T, L extends PropertyKey> = {
  [P in keyof T]: T[P] extends infer TP ? {
    [Q in keyof TP]: [P, Q] extends [K, L] ? never : TP[Q]
  } : never
}

// AppearsIn2d<T, V, Y, N> takes a nested tuple T and a value V, 
// and returns Y if the value V is assignable to any element of any element of T
// and returns N otherwise
type AppearsIn2D<T, V, Y = unknown, N = never> = unknown extends {
  [P in keyof T]: T[P] extends infer TP ? {
    [Q in keyof TP]: V extends TP[Q] ? unknown : never
  }[keyof TP] : never }[keyof T] ? Y : N

// Invalid<T> makes an error message in lieu of custom invalid types 
// (see microsoft/typescript#23689)
type Invalid<T> = Error & { __errorMessage: T };

// UniquifyTwoD<T> takes a 2-d nested tuple T and returns T iff no repeats
// appear, otherwise it replaces offending repeated elements with an Invalid<>
type UniquifyTwoD<T extends ReadonlyArray<ReadonlyArray<any>>> = {
  [P in keyof T]: T[P] extends infer TP ? {
    [Q in keyof TP]: AppearsIn2D<BlankOut2D<T, P, Q>, TP[Q], Invalid<[TP[Q], "is repeated"]>, TP[Q]>
  } : never
}

// helper function
const asUnique2DSmthArray = <
  A extends ([[]] | (ReadonlyArray<ReadonlyArray<Smth>>)) & UniquifyTwoD<A>
>(
  a: A
) => a;

And it works like this:

const x = asUnique2DSmthArray([
  [Smth.a, Smth.b],
  [Smth.d],
]); // okay

const y = asUnique2DSmthArray([
  [Smth.a, Smth.b, Smth.a], // error!
  //~~~~~          ~~~~~~ <-- not assignable to Invalid<[Smth.a, "is repeated"]>
  [Smth.d], 
]); 

const z = asUnique2DSmthArray([
  [Smth.a, Smth.b], // error! 
  //~~~~~ <-- Invalid<[Smth.a, "is repeated"]
  [Smth.d, Smth.a], // error!
  //~~~~~, ~~~~~~ <-- Invalid<[Smth.a | Smth.d, "is repeated"]>   
]);

That pretty much works except the error when the repeated element spans arrays is not perfect. The problem is that the failure of assignability causes the compiler to widen the type of the second argument from [Smth.d, Smth.a] to Array<Smth.d | Smth.a>, and then it complains about the whole argument being repeated. But I can't figure out how to prevent that from happening.

Okay, hope that helps; good luck!

Link to code

Disallow duplicates in array

1 Answers1