String Iterator Pattern

[ecyrbe]

Hello @sno2 ,

I open here a discussion about your optimisation.
From what i understand, your whole cache is actually an iterator, and i'd say a string iterator to match at least a number of strings.

I think we should abstract that away to make the algorithm clearer to understand and maintain.
Here are the operations i think should be abstracted :

export namespace StringIterator {
  type Iterator = { pattern: string; index: number };
  type Make = { pattern: `$${string}`; index: 0 }; // create an iterator for a string on size 0+
  type Next<It extends Iterator> = <to implement>;
  type Prev<It extends Iterator> = <to implement>;
  type Double<It extends Iterator> = <to implement>;
  type Diff<It1 extends Iterator, It2> = <to implement>;
  type IsStringMatchingIterator<Str extends string, It> = <to implement>;
}

tell me if i'm correct, are those the operations you are using in the Length algorithm ?
If so, could you implement them ? This way we will be able to leverage generic algorithms based on this StringIterator.

[sno2]

Hello, yes, the string length algorithm basically works like the following JavaScript-like code if you assume the acc starts with a single character that will match any single character in the s.

function length(s, acc) {
    if (s === "") {
        return 0;
    } else if (s.indexOf(acc) === 0) {
        return acc.length + length(s.slice(acc.length), acc + acc);
    } else {
        return length(s, acc.slice(acc.length / 2));
    }
}

length("000000", "0"); // 6
length("00", "0"); // 2

The problem is that generating the acc requires quite a bit of work because ${string}${string} is eagerly reduced to ${string}. Therefore, we need to keep a dollar sign at the beginning and include an underscore at the end which we later take out when concatenating two of the patterns. However, I believe the same approach can still be used as you have done so in Repeat with a bit more work due to the limitation of creating the patterns. I will try to implement the utils as you have described.

[ecyrbe]

@sno2
for now i was hable to simplify your algorithm using this :

export namespace StringIterator {
  export type Iterator = [string, number | bigint];
  export type Init = [`$${string}`, 1];
  export type Next<It extends Iterator> = [`${It[0]}${string}`, Add<It[1], 1>];
  export type Double<It extends Iterator> =
    `${It[0]}_` extends `$${infer pattern}`
      ? `${It[0]}${pattern}` extends `${infer double}_`
        ? [double, Mul<It[1], 2>]
        : never
      : never;
}

type LengthUp<
  T extends string,
  $Length extends number | bigint = 0,
  $Cache extends StringIterator.Iterator[] = [StringIterator.Init]
> =
  //
  $Cache extends [
    infer It extends StringIterator.Iterator,
    ...infer $RestCache extends StringIterator.Iterator[]
  ]
    ? StringIterator.Double<It> extends infer $DoubleIt extends StringIterator.Iterator
      ? `$${T}` extends `${$DoubleIt[0]}${infer $Rest}`
        ? $Cache["length"] extends 12 // 2^13 is the last block size within the complexity limit
          ? LengthDown<
              $Rest,
              Add<$Length, $DoubleIt[1]>,
              [$DoubleIt, ...$Cache]
            >
          : LengthUp<$Rest, Add<$Length, $DoubleIt[1]>, [$DoubleIt, ...$Cache]>
        : `$${T}` extends `${It[0]}${infer $Rest}`
        ? LengthUp<$Rest, Add<$Length, It[1]>, $Cache>
        : LengthDown<T, $Length, $RestCache>
      : never
    : $Length;

type LengthDown<
  T extends string,
  $Length extends number | bigint,
  $Cache extends StringIterator.Iterator[]
> = $Cache extends [
  infer It extends StringIterator.Iterator,
  ...infer $RestCache extends StringIterator.Iterator[]
]
  ? `$${T}` extends `${It[0]}${infer $Rest}`
    ? LengthDown<$Rest, Add<$Length, It[1]>, $Cache>
    : LengthDown<T, $Length, $RestCache>
  : $Length;

export type Length<T extends string> = T extends "" ? 0 : LengthUp<T>;

[sno2]

Really nice work! (nit: `${double}` could be just double)

[ecyrbe]

indeed

[ecyrbe]

do you think you can simplify it further ?

[ecyrbe]

I improved it further, here is the PR: #38