1
/*
2
 *  This file is part of CoCalc: Copyright © 2020 Sagemath, Inc.
3
 *  License: MS-RSL – see LICENSE.md for details
4
 */
5

6
export { get_start_time_ts, get_uptime, log, wrap_log } from "./log";
7

8
export * from "./misc-path";
9

10
import LRU from "lru-cache";
11

12
import {
13
  is_array,
14
  is_integer,
15
  is_object,
16
  is_string,
17
  is_date,
18
  is_set,
19
} from "./type-checking";
20

21
export { is_array, is_integer, is_object, is_string, is_date, is_set };
22

23
export {
24
  map_limit,
25
  map_max,
26
  map_min,
27
  sum,
28
  is_zero_map,
29
  map_without_undefined_and_null,
30
  map_mutate_out_undefined_and_null,
31
} from "./maps";
32

33
export { done, done1, done2 } from "./done";
34

35
export {
36
  cmp,
37
  cmp_Date,
38
  cmp_dayjs,
39
  cmp_moment,
40
  cmp_array,
41
  timestamp_cmp,
42
  field_cmp,
43
  is_different,
44
  is_different_array,
45
  shallowCompare,
46
  all_fields_equal,
47
} from "./cmp";
48

49
export {
50
  server_time,
51
  server_milliseconds_ago,
52
  server_seconds_ago,
53
  server_minutes_ago,
54
  server_hours_ago,
55
  server_days_ago,
56
  server_weeks_ago,
57
  server_months_ago,
58
  milliseconds_before,
59
  seconds_before,
60
  minutes_before,
61
  hours_before,
62
  days_before,
63
  weeks_before,
64
  months_before,
65
  expire_time,
66
  YEAR,
67
} from "./relative-time";
68

69
import sha1 from "sha1";
70
export { sha1 };
71

72
function base16ToBase64(hex) {
73
  return Buffer.from(hex, "hex").toString("base64");
74
  //   let bytes: number[] = [];
75
  //   for (let c = 0; c < hex.length; c += 2) {
76
  //     bytes.push(parseInt(hex.substr(c, 2), 16));
77
  //   }
78
  //   return btoa(String.fromCharCode.apply(null, bytes));
79
}
80

81
export function sha1base64(s) {
82
  return base16ToBase64(sha1(s));
83
}
84

85
import getRandomValues from "get-random-values";
86
import * as lodash from "lodash";
87
import * as immutable from "immutable";
88

89
export const keys: (any) => string[] = lodash.keys;
90

91
import { required, defaults, types } from "./opts";
92
export { required, defaults, types };
93

94
interface SplittedPath {
95
  head: string;
96
  tail: string;
97
}
98

99
export function path_split(path: string): SplittedPath {
100
  const v = path.split("/");
101
  return { head: v.slice(0, -1).join("/"), tail: v[v.length - 1] };
102
}
103

104
// NOTE: as of right now, there is definitely some code somewhere
105
// in cocalc that calls this sometimes with s undefined, and
106
// typescript doesn't catch it, hence allowing s to be undefined.
107
export function capitalize(s?: string): string {
108
  if (!s) return "";
109
  return s.charAt(0).toUpperCase() + s.slice(1);
110
}
111

112
// turn an arbitrary string into a nice clean identifier that can safely be used in an URL
113
export function make_valid_name(s: string): string {
114
  // for now we just delete anything that isn't alphanumeric.
115
  // See http://stackoverflow.com/questions/9364400/remove-not-alphanumeric-characters-from-string-having-trouble-with-the-char/9364527#9364527
116
  // whose existence surprised me!
117
  return s.replace(/\W/g, "_").toLowerCase();
118
}
119

120
const filename_extension_re = /(?:\.([^.]+))?$/;
121
export function filename_extension(filename: string): string {
122
  filename = path_split(filename).tail;
123
  const match = filename_extension_re.exec(filename);
124
  if (!match) {
125
    return "";
126
  }
127
  const ext = match[1];
128
  return ext ? ext : "";
129
}
130

131
export function filename_extension_notilde(filename: string): string {
132
  let ext = filename_extension(filename);
133
  while (ext && ext[ext.length - 1] === "~") {
134
    // strip tildes from the end of the extension -- put there by rsync --backup, and other backup systems in UNIX.
135
    ext = ext.slice(0, ext.length - 1);
136
  }
137
  return ext;
138
}
139

140
// If input name foo.bar, returns object {name:'foo', ext:'bar'}.
141
// If there is no . in input name, returns {name:name, ext:''}
142
export function separate_file_extension(name: string): {
143
  name: string;
144
  ext: string;
145
} {
146
  const ext: string = filename_extension(name);
147
  if (ext !== "") {
148
    name = name.slice(0, name.length - ext.length - 1); // remove the ext and the .
149
  }
150
  return { name, ext };
151
}
152

153
// change the filename's extension to the new one.
154
// if there is no extension, add it.
155
export function change_filename_extension(
156
  path: string,
157
  new_ext: string,
158
): string {
159
  const { name } = separate_file_extension(path);
160
  return `${name}.${new_ext}`;
161
}
162

163
// Takes parts to a path and intelligently merges them on '/'.
164
// Continuous non-'/' portions of each part will have at most
165
// one '/' on either side.
166
// Each part will have exactly one '/' between it and adjacent parts
167
// Does NOT resolve up-level references
168
// See misc-tests for examples.
169
export function normalized_path_join(...parts): string {
170
  const sep = "/";
171
  const replace = new RegExp(sep + "{1,}", "g");
172
  const result: string[] = [];
173
  for (let x of Array.from(parts)) {
174
    if (x != null && `${x}`.length > 0) {
175
      result.push(`${x}`);
176
    }
177
  }
178
  return result.join(sep).replace(replace, sep);
179
}
180

181
// Like Python splitlines.
182
// WARNING -- this is actually NOT like Python splitlines, since it just deletes whitespace lines. TODO: audit usage and fix.
183
export function splitlines(s: string): string[] {
184
  const r = s.match(/[^\r\n]+/g);
185
  return r ? r : [];
186
}
187

188
// Like Python's string split -- splits on whitespace
189
export function split(s: string): string[] {
190
  const r = s.match(/\S+/g);
191
  if (r) {
192
    return r;
193
  } else {
194
    return [];
195
  }
196
}
197

198
// Modifies in place the object dest so that it
199
// includes all values in objs and returns dest.
200
// This is a *shallow* copy.
201
// Rightmost object overwrites left.
202
export function merge(dest, ...objs) {
203
  for (const obj of objs) {
204
    for (const k in obj) {
205
      dest[k] = obj[k];
206
    }
207
  }
208
  return dest;
209
}
210

211
// Makes new object that is *shallow* copy merge of all objects.
212
export function merge_copy(...objs): object {
213
  return merge({}, ...Array.from(objs));
214
}
215

216
// copy of map but only with some keys
217
// I.e., restrict a function to a subset of the domain.
218
export function copy_with<T>(obj: T, w: string | string[]): Partial<T> {
219
  if (typeof w === "string") {
220
    w = [w];
221
  }
222
  const obj2: any = {};
223
  let key: string;
224
  for (key of w) {
225
    const y = obj[key];
226
    if (y !== undefined) {
227
      obj2[key] = y;
228
    }
229
  }
230
  return obj2;
231
}
232

233
// copy of map but without some keys
234
// I.e., restrict a function to the complement of a subset of the domain.
235
export function copy_without(obj: object, w: string | string[]): object {
236
  if (typeof w === "string") {
237
    w = [w];
238
  }
239
  const r = {};
240
  for (let key in obj) {
241
    const y = obj[key];
242
    if (!Array.from(w).includes(key)) {
243
      r[key] = y;
244
    }
245
  }
246
  return r;
247
}
248

249
import { cloneDeep } from "lodash";
250
export const deep_copy = cloneDeep;
251

252
// Very poor man's set.
253
export function set(v: string[]): { [key: string]: true } {
254
  const s: { [key: string]: true } = {};
255
  for (const x of v) {
256
    s[x] = true;
257
  }
258
  return s;
259
}
260

261
// see https://stackoverflow.com/questions/728360/how-do-i-correctly-clone-a-javascript-object/30042948#30042948
262
export function copy<T>(obj: T): T {
263
  return lodash.clone(obj);
264
}
265

266
// startswith(s, x) is true if s starts with the string x or any of the strings in x.
267
// It is false if s is not a string.
268
export function startswith(s: any, x: string | string[]): boolean {
269
  if (typeof s != "string") {
270
    return false;
271
  }
272
  if (typeof x === "string") {
273
    return s.startsWith(x);
274
  }
275
  for (const v of x) {
276
    if (s.indexOf(v) === 0) {
277
      return true;
278
    }
279
  }
280
  return false;
281
}
282

283
export function endswith(s: any, t: any): boolean {
284
  if (typeof s != "string" || typeof t != "string") {
285
    return false;
286
  }
287
  return s.endsWith(t);
288
}
289

290
import { v4 as v4uuid } from "uuid";
291
export const uuid: () => string = v4uuid;
292

293
const uuid_regexp = new RegExp(
294
  /[a-fA-F0-9]{8}-[a-fA-F0-9]{4}-[a-fA-F0-9]{4}-[a-fA-F0-9]{4}-[a-fA-F0-9]{12}/i,
295
);
296
export function is_valid_uuid_string(uuid?: any): boolean {
297
  return (
298
    typeof uuid === "string" && uuid.length === 36 && uuid_regexp.test(uuid)
299
  );
300
}
301
export function assert_valid_account_id(uuid?: any): void {
302
  if (!is_valid_uuid_string(uuid)) {
303
    throw new Error(`Invalid Account ID: ${uuid}`);
304
  }
305
}
306
export const isValidUUID = is_valid_uuid_string;
307

308
export function assertValidAccountID(account_id?: any) {
309
  if (!isValidUUID(account_id)) {
310
    throw Error("account_id is invalid");
311
  }
312
}
313

314
export function assert_uuid(uuid: string): void {
315
  if (!is_valid_uuid_string(uuid)) {
316
    throw Error(`invalid uuid='${uuid}'`);
317
  }
318
}
319

320
// Compute a uuid v4 from the Sha-1 hash of data.
321
// NOTE: If on backend, you should instead import
322
// the version in misc_node, which is faster.
323
export function uuidsha1(data: string): string {
324
  const s = sha1(data);
325
  let i = -1;
326
  return "xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx".replace(/[xy]/g, function (c) {
327
    i += 1;
328
    switch (c) {
329
      case "x":
330
        return s[i];
331
      case "y":
332
        // take 8 + low order 3 bits of hex number.
333
        return ((parseInt(`0x${s[i]}`, 16) & 0x3) | 0x8).toString(16);
334
    }
335
  });
336
}
337

338
// returns the number of keys of an object, e.g., {a:5, b:7, d:'hello'} --> 3
339
export function len(obj: object | undefined | null): number {
340
  if (obj == null) {
341
    return 0;
342
  }
343
  return Object.keys(obj).length;
344
}
345

346
// Specific, easy to read: describe amount of time before right now
347
// Use negative input for after now (i.e., in the future).
348
export function milliseconds_ago(ms: number): Date {
349
  return new Date(Date.now() - ms);
350
}
351
export function seconds_ago(s: number) {
352
  return milliseconds_ago(1000 * s);
353
}
354
export function minutes_ago(m: number) {
355
  return seconds_ago(60 * m);
356
}
357
export function hours_ago(h: number) {
358
  return minutes_ago(60 * h);
359
}
360
export function days_ago(d: number) {
361
  return hours_ago(24 * d);
362
}
363
export function weeks_ago(w: number) {
364
  return days_ago(7 * w);
365
}
366
export function months_ago(m: number) {
367
  return days_ago(30.5 * m);
368
}
369

370
// Here, we want to know how long ago a certain timestamp was
371
export function how_long_ago_ms(ts: Date | number): number {
372
  const ts_ms = typeof ts === "number" ? ts : ts.getTime();
373
  return Date.now() - ts_ms;
374
}
375
export function how_long_ago_s(ts: Date | number): number {
376
  return how_long_ago_ms(ts) / 1000;
377
}
378
export function how_long_ago_m(ts: Date | number): number {
379
  return how_long_ago_s(ts) / 60;
380
}
381

382
// Current time in milliseconds since epoch or t.
383
export function mswalltime(t?: number): number {
384
  return Date.now() - (t ?? 0);
385
}
386

387
// Current time in seconds since epoch, as a floating point
388
// number (so much more precise than just seconds), or time
389
// since t.
390
export function walltime(t?: number): number {
391
  return mswalltime() / 1000.0 - (t ?? 0);
392
}
393

394
// encode a UNIX path, which might have # and % in it.
395
// Maybe alternatively, (encodeURIComponent(p) for p in path.split('/')).join('/') ?
396
export function encode_path(path) {
397
  // doesn't escape # and ?, since they are special for urls (but not unix paths)
398
  path = encodeURI(path);
399
  return path.replace(/#/g, "%23").replace(/\?/g, "%3F");
400
}
401

402
const reValidEmail = (function () {
403
  const sQtext = "[^\\x0d\\x22\\x5c\\x80-\\xff]";
404
  const sDtext = "[^\\x0d\\x5b-\\x5d\\x80-\\xff]";
405
  const sAtom =
406
    "[^\\x00-\\x20\\x22\\x28\\x29\\x2c\\x2e\\x3a-\\x3c\\x3e\\x40\\x5b-\\x5d\\x7f-\\xff]+";
407
  const sQuotedPair = "\\x5c[\\x00-\\x7f]";
408
  const sDomainLiteral = `\\x5b(${sDtext}|${sQuotedPair})*\\x5d`;
409
  const sQuotedString = `\\x22(${sQtext}|${sQuotedPair})*\\x22`;
410
  const sDomain_ref = sAtom;
411
  const sSubDomain = `(${sDomain_ref}|${sDomainLiteral})`;
412
  const sWord = `(${sAtom}|${sQuotedString})`;
413
  const sDomain = sSubDomain + "(\\x2e" + sSubDomain + ")*";
414
  const sLocalPart = sWord + "(\\x2e" + sWord + ")*";
415
  const sAddrSpec = sLocalPart + "\\x40" + sDomain; // complete RFC822 email address spec
416
  const sValidEmail = `^${sAddrSpec}$`; // as whole string
417
  return new RegExp(sValidEmail);
418
})();
419

420
export function is_valid_email_address(email: string): boolean {
421
  // From http://stackoverflow.com/questions/46155/validate-email-address-in-javascript
422
  // but converted to Javascript; it's near the middle but claims to be exactly RFC822.
423
  if (reValidEmail.test(email)) {
424
    return true;
425
  } else {
426
    return false;
427
  }
428
}
429

430
export function assert_valid_email_address(email: string): void {
431
  if (!is_valid_email_address(email)) {
432
    throw Error(`Invalid email address: ${email}`);
433
  }
434
}
435

436
export const to_json = JSON.stringify;
437

438
// gives the plural form of the word if the number should be plural
439
export function plural(
440
  number: number = 0,
441
  singular: string,
442
  plural: string = `${singular}s`,
443
) {
444
  if (["GB", "G", "MB"].includes(singular)) {
445
    return singular;
446
  }
447
  if (number === 1) {
448
    return singular;
449
  } else {
450
    return plural;
451
  }
452
}
453

454
const ELLIPSIS = "…";
455
// "foobar" --> "foo…"
456
export function trunc<T>(
457
  sArg: T,
458
  max_length = 1024,
459
  ellipsis = ELLIPSIS,
460
): string | T {
461
  if (sArg == null) {
462
    return sArg;
463
  }
464
  const s = typeof sArg !== "string" ? `${sArg}` : sArg;
465
  if (s.length > max_length) {
466
    if (max_length < 1) {
467
      throw new Error("ValueError: max_length must be >= 1");
468
    }
469
    return s.slice(0, max_length - 1) + ellipsis;
470
  } else {
471
    return s;
472
  }
473
}
474

475
// "foobar" --> "fo…ar"
476
export function trunc_middle<T>(
477
  sArg: T,
478
  max_length = 1024,
479
  ellipsis = ELLIPSIS,
480
): T | string {
481
  if (sArg == null) {
482
    return sArg;
483
  }
484
  const s = typeof sArg !== "string" ? `${sArg}` : sArg;
485
  if (s.length <= max_length) {
486
    return s;
487
  }
488
  if (max_length < 1) {
489
    throw new Error("ValueError: max_length must be >= 1");
490
  }
491
  const n = Math.floor(max_length / 2);
492
  return (
493
    s.slice(0, n - 1 + (max_length % 2 ? 1 : 0)) +
494
    ellipsis +
495
    s.slice(s.length - n)
496
  );
497
}
498

499
// "foobar" --> "…bar"
500
export function trunc_left<T>(
501
  sArg: T,
502
  max_length = 1024,
503
  ellipsis = ELLIPSIS,
504
): T | string  {
505
  if (sArg == null) {
506
    return sArg;
507
  }
508
  const s = typeof sArg !== "string" ? `${sArg}` : sArg;
509
  if (s.length > max_length) {
510
    if (max_length < 1) {
511
      throw new Error("ValueError: max_length must be >= 1");
512
    }
513
    return ellipsis + s.slice(s.length - max_length + 1);
514
  } else {
515
    return s;
516
  }
517
}
518

519
/*
520
Like the immutable.js getIn, but on the thing x.
521
*/
522

523
export function getIn(x: any, path: string[], default_value?: any): any {
524
  for (const key of path) {
525
    if (x !== undefined) {
526
      try {
527
        x = x[key];
528
      } catch (err) {
529
        return default_value;
530
      }
531
    } else {
532
      return default_value;
533
    }
534
  }
535
  return x === undefined ? default_value : x;
536
}
537

538
// see http://stackoverflow.com/questions/1144783/replacing-all-occurrences-of-a-string-in-javascript
539
export function replace_all(
540
  s: string,
541
  search: string,
542
  replace: string,
543
): string {
544
  return s.split(search).join(replace);
545
}
546

547
// Similar to replace_all, except it takes as input a function replace_f, which
548
// returns what to replace the i-th copy of search in string with.
549
export function replace_all_function(
550
  s: string,
551
  search: string,
552
  replace_f: (i: number) => string,
553
): string {
554
  const v = s.split(search);
555
  const w: string[] = [];
556
  for (let i = 0; i < v.length; i++) {
557
    w.push(v[i]);
558
    if (i < v.length - 1) {
559
      w.push(replace_f(i));
560
    }
561
  }
562
  return w.join("");
563
}
564

565
export function path_to_title(path: string): string {
566
  const subtitle = separate_file_extension(path_split(path).tail).name;
567
  return capitalize(replace_all(replace_all(subtitle, "-", " "), "_", " "));
568
}
569

570
// names is a Set<string>
571
export function list_alternatives(names): string {
572
  names = names.map((x) => x.toUpperCase()).toJS();
573
  if (names.length == 1) {
574
    return names[0];
575
  } else if (names.length == 2) {
576
    return `${names[0]} or ${names[1]}`;
577
  }
578
  return names.join(", ");
579
}
580

581
// convert x to a useful string to show to a user.
582
export function to_user_string(x: any): string {
583
  switch (typeof x) {
584
    case "undefined":
585
      return "undefined";
586
    case "number":
587
    case "symbol":
588
    case "boolean":
589
      return x.toString();
590
    case "function":
591
      return x.toString();
592
    case "object":
593
      if (typeof x.toString !== "function") {
594
        return JSON.stringify(x);
595
      }
596
      const a = x.toString(); // is much better than stringify for exceptions (etc.).
597
      if (a === "[object Object]") {
598
        return JSON.stringify(x);
599
      } else {
600
        return a;
601
      }
602
    default:
603
      return JSON.stringify(x);
604
  }
605
}
606

607
// delete any null fields, to avoid wasting space.
608
export function delete_null_fields(obj: object): void {
609
  for (const k in obj) {
610
    if (obj[k] == null) {
611
      delete obj[k];
612
    }
613
  }
614
}
615

616
// for switch/case -- https://www.typescriptlang.org/docs/handbook/advanced-types.html
617
export function unreachable(x: never) {
618
  // if this fails a typecheck here, go back to your switch/case.
619
  // you either made a typo in one of the cases or you missed one.
620
  const tmp: never = x;
621
  tmp;
622
}
623

624
// Get *all* methods of an object (including from base classes!).
625
// See https://flaviocopes.com/how-to-list-object-methods-javascript/
626
// This is used by bind_methods below to bind all methods
627
// of an instance of an object, all the way up the
628
// prototype chain, just to be 100% sure!
629
function get_methods(obj: object): string[] {
630
  let properties = new Set<string>();
631
  let current_obj = obj;
632
  do {
633
    Object.getOwnPropertyNames(current_obj).map((item) => properties.add(item));
634
  } while ((current_obj = Object.getPrototypeOf(current_obj)));
635
  return [...properties.keys()].filter(
636
    (item) => typeof obj[item] === "function",
637
  );
638
}
639

640
// Bind all or specified methods of the object.  If method_names
641
// is not given, binds **all** methods.
642
// For example, in a base class constructor, you can do
643
//       bind_methods(this);
644
// and every method will always be bound even for derived classes
645
// (assuming they call super if they overload the constructor!).
646
// Do this for classes that don't get created in a tight inner
647
// loop and for which you want 'safer' semantics.
648
export function bind_methods<T extends object>(
649
  obj: T,
650
  method_names: undefined | string[] = undefined,
651
): T {
652
  if (method_names === undefined) {
653
    method_names = get_methods(obj);
654
    method_names.splice(method_names.indexOf("constructor"), 1);
655
  }
656
  for (const method_name of method_names) {
657
    obj[method_name] = obj[method_name].bind(obj);
658
  }
659
  return obj;
660
}
661

662
export function human_readable_size(
663
  bytes: number | null | undefined,
664
  short = false,
665
): string {
666
  if (bytes == null) {
667
    return "?";
668
  }
669
  if (bytes < 1000) {
670
    return `${bytes} ${short ? "b" : "bytes"}`;
671
  }
672
  if (bytes < 1000000) {
673
    const b = Math.floor(bytes / 100);
674
    return `${b / 10} KB`;
675
  }
676
  if (bytes < 1000000000) {
677
    const b = Math.floor(bytes / 100000);
678
    return `${b / 10} MB`;
679
  }
680
  const b = Math.floor(bytes / 100000000);
681
  return `${b / 10} GB`;
682
}
683

684
// Regexp used to test for URLs in a string.
685
// We just use a simple one that was a top Google search when I searched: https://www.regextester.com/93652
686
// We don't use a complicated one like https://www.npmjs.com/package/url-regex, since
687
// (1) it is heavy and doesn't work on Edge -- https://github.com/sagemathinc/cocalc/issues/4056
688
// (2) it's not bad if we are extra conservative.  E.g., url-regex "matches the TLD against a list of valid TLDs."
689
//     which is really overkill for preventing abuse, and is clearly more aimed at highlighting URL's
690
//     properly (not our use case).
691
export const re_url =
692
  /(http:\/\/www\.|https:\/\/www\.|http:\/\/|https:\/\/)?[a-z0-9]+([\-\.]{1}[a-z0-9]+)*\.[a-z]{2,5}(:[0-9]{1,5})?(\/.*)?/gi;
693

694
export function contains_url(str: string): boolean {
695
  return !!str.toLowerCase().match(re_url);
696
}
697

698
export function hidden_meta_file(path: string, ext: string): string {
699
  const p = path_split(path);
700
  let head: string = p.head;
701
  if (head !== "") {
702
    head += "/";
703
  }
704
  return head + "." + p.tail + "." + ext;
705
}
706

707
export function history_path(path: string): string {
708
  return hidden_meta_file(path, "time-travel");
709
}
710

711
export function meta_file(path: string, ext: string): string {
712
  return hidden_meta_file(path, "sage-" + ext);
713
}
714

715
// helps with converting an array of strings to a union type of strings.
716
// usage: 1. const foo : string[] = tuple(["bar", "baz"]);
717
//        2. type Foo = typeof foo[number]; // bar | baz;
718
//
719
// NOTE: in newer TS versions, it's fine to define the string[] list with "as const", then step 2.
720
export function tuple<T extends string[]>(o: T) {
721
  return o;
722
}
723

724
export function aux_file(path: string, ext: string): string {
725
  const s = path_split(path);
726
  s.tail += "." + ext;
727
  if (s.head) {
728
    return s.head + "/." + s.tail;
729
  } else {
730
    return "." + s.tail;
731
  }
732
}
733

734
export function auxFileToOriginal(path: string): string {
735
  const { head, tail } = path_split(path);
736
  const i = tail.lastIndexOf(".");
737
  const filename = tail.slice(1, i);
738
  if (!head) {
739
    return filename;
740
  }
741
  return head + "/" + filename;
742
}
743

744
/*
745
Generate a cryptographically safe secure random string with
746
16 characters chosen to be reasonably unambiguous to look at.
747
That is 93 bits of randomness, and there is an argument here
748
that 64 bits is enough:
749

750
https://security.stackexchange.com/questions/1952/how-long-should-a-random-nonce-be
751
*/
752
const BASE58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
753
export function secure_random_token(
754
  length: number = 16,
755
  alphabet: string = BASE58, // default is this crypto base58 less ambiguous numbers/letters
756
): string {
757
  let s = "";
758
  if (length == 0) return s;
759
  if (alphabet.length == 0) {
760
    throw Error("impossible, since alphabet is empty");
761
  }
762
  const v = new Uint8Array(length);
763
  getRandomValues(v); // secure random numbers
764
  for (const i of v) {
765
    s += alphabet[i % alphabet.length];
766
  }
767
  return s;
768
}
769

770
// Return a random element of an array.
771
// If array has length 0 will return undefined.
772
export function random_choice(v: any[]): any {
773
  return v[Math.floor(Math.random() * v.length)];
774
}
775

776
// Called when an object will not be used further, to avoid
777
// it references anything that could lead to memory leaks.
778

779
export function close(obj: object, omit?: Set<string>): void {
780
  if (omit != null) {
781
    Object.keys(obj).forEach(function (key) {
782
      if (omit.has(key)) return;
783
      if (typeof obj[key] == "function") return;
784
      delete obj[key];
785
    });
786
  } else {
787
    Object.keys(obj).forEach(function (key) {
788
      if (typeof obj[key] == "function") return;
789
      delete obj[key];
790
    });
791
  }
792
}
793

794
// return true if the word contains the substring
795
export function contains(word: string, sub: string): boolean {
796
  return word.indexOf(sub) !== -1;
797
}
798

799
export function assertDefined<T>(val: T): asserts val is NonNullable<T> {
800
  if (val === undefined || val === null) {
801
    throw new Error(`Expected 'val' to be defined, but received ${val}`);
802
  }
803
}
804

805
export function round1(num: number): number {
806
  return Math.round(num * 10) / 10;
807
}
808

809
// Round given number to 2 decimal places
810
export function round2(num: number): number {
811
  // padding to fix floating point issue (see http://stackoverflow.com/questions/11832914/round-to-at-most-2-decimal-places-in-javascript)
812
  return Math.round((num + 0.00001) * 100) / 100;
813
}
814

815
export function round3(num: number): number {
816
  return Math.round((num + 0.000001) * 1000) / 1000;
817
}
818

819
export function round4(num: number): number {
820
  return Math.round((num + 0.0000001) * 10000) / 10000;
821
}
822

823
// Round given number up to 2 decimal places, for the
824
// purposes of dealing with money.  We use toFixed to
825
// accomplish this, because we care about the decimal
826
// representation, not the exact internal binary number.
827
// Doing ' Math.ceil(num * 100) / 100', is wrong because
828
// e.g., numbers like 4.73 are not representable in binary, e.g.,
829
//  >  4.73 = 100.101110101110000101000111101011100001010001111011... forever
830
export function round2up(num: number): number {
831
  // This rounds the number to the closest 2-digit decimal representation.
832
  // It can be LESS than num, e.g., (0.356).toFixed(2) == '0.36'
833
  const rnd = parseFloat(num.toFixed(2));
834
  if (rnd >= num) {
835
    // it  rounded up.
836
    return rnd;
837
  }
838
  // It rounded down, so we add a penny to num first,
839
  // to ensure that rounding is up.
840
  return parseFloat((num + 0.01).toFixed(2));
841
}
842

843
// Round given number down to 2 decimal places, suitable for
844
// dealing with money.
845
export function round2down(num: number): number {
846
  // This rounds the number to the closest 2-digit decimal representation.
847
  // It can be LESS than num, e.g., (0.356).toFixed(2) == '0.36'
848
  const rnd = parseFloat(num.toFixed(2));
849
  if (rnd <= num) {
850
    // it rounded down: good.
851
    return rnd;
852
  }
853
  // It rounded up, so we subtract a penny to num first,
854
  // to ensure that rounding is down.
855
  return parseFloat((num - 0.01).toFixed(2));
856
}
857

858
// returns the number parsed from the input text, or undefined if invalid
859
// rounds to the nearest 0.01 if round_number is true (default : true)
860
// allows negative numbers if allow_negative is true (default : false)
861
export function parse_number_input(
862
  input: any,
863
  round_number: boolean = true,
864
  allow_negative: boolean = false,
865
): number | undefined {
866
  if (typeof input == "boolean") {
867
    return input ? 1 : 0;
868
  }
869

870
  if (typeof input == "number") {
871
    // easy to parse
872
    if (!isFinite(input)) {
873
      return;
874
    }
875
    if (!allow_negative && input < 0) {
876
      return;
877
    }
878
    return input;
879
  }
880

881
  if (input == null || !input) return 0;
882

883
  let val;
884
  const v = `${input}`.split("/"); // fraction?
885
  if (v.length !== 1 && v.length !== 2) {
886
    return undefined;
887
  }
888
  if (v.length === 2) {
889
    // a fraction
890
    val = parseFloat(v[0]) / parseFloat(v[1]);
891
  }
892
  if (v.length === 1) {
893
    val = parseFloat(v[0]);
894
    if (isNaN(val) || v[0].trim() === "") {
895
      // Shockingly, whitespace returns false for isNaN!
896
      return undefined;
897
    }
898
  }
899
  if (round_number) {
900
    val = round2(val);
901
  }
902
  if (isNaN(val) || val === Infinity || (val < 0 && !allow_negative)) {
903
    return undefined;
904
  }
905
  return val;
906
}
907

908
// MUTATE map by coercing each element of codomain to a number,
909
// with false->0 and true->1
910
// Non finite values coerce to 0.
911
// Also, returns map.
912
export function coerce_codomain_to_numbers(map: { [k: string]: any }): {
913
  [k: string]: number;
914
} {
915
  for (const k in map) {
916
    const x = map[k];
917
    if (typeof x === "boolean") {
918
      map[k] = x ? 1 : 0;
919
    } else {
920
      try {
921
        const t = parseFloat(x);
922
        if (isFinite(t)) {
923
          map[k] = t;
924
        } else {
925
          map[k] = 0;
926
        }
927
      } catch (_) {
928
        map[k] = 0;
929
      }
930
    }
931
  }
932
  return map;
933
}
934

935
// arithmetic of maps with codomain numbers; missing values
936
// default to 0.  Despite the typing being that codomains are
937
// all numbers, we coerce null values to 0 as well, and all codomain
938
// values to be numbers, since definitely some client code doesn't
939
// pass in properly typed inputs.
940
export function map_sum(
941
  a?: { [k: string]: number },
942
  b?: { [k: string]: number },
943
): { [k: string]: number } {
944
  if (a == null) {
945
    return coerce_codomain_to_numbers(b ?? {});
946
  }
947
  if (b == null) {
948
    return coerce_codomain_to_numbers(a ?? {});
949
  }
950
  a = coerce_codomain_to_numbers(a);
951
  b = coerce_codomain_to_numbers(b);
952
  const c: { [k: string]: number } = {};
953
  for (const k in a) {
954
    c[k] = (a[k] ?? 0) + (b[k] ?? 0);
955
  }
956
  for (const k in b) {
957
    if (c[k] == null) {
958
      // anything in iteration above will be a number; also,
959
      // we know a[k] is null, since it was definintely not
960
      // iterated through above.
961
      c[k] = b[k] ?? 0;
962
    }
963
  }
964
  return c;
965
}
966

967
export function map_diff(
968
  a?: { [k: string]: number },
969
  b?: { [k: string]: number },
970
): { [k: string]: number } {
971
  if (b == null) {
972
    return coerce_codomain_to_numbers(a ?? {});
973
  }
974
  b = coerce_codomain_to_numbers(b);
975
  const c: { [k: string]: number } = {};
976
  if (a == null) {
977
    for (const k in b) {
978
      c[k] = -(b[k] ?? 0);
979
    }
980
    return c;
981
  }
982
  a = coerce_codomain_to_numbers(a);
983
  for (const k in a) {
984
    c[k] = (a[k] ?? 0) - (b[k] ?? 0);
985
  }
986
  for (const k in b) {
987
    if (c[k] == null) {
988
      // anything in iteration above will be a number; also,
989
      // we know a[k] is null, since it was definintely not
990
      // iterated through above.
991
      c[k] = -(b[k] ?? 0);
992
    }
993
  }
994
  return c;
995
}
996

997
// Like the split method, but quoted terms are grouped
998
// together for an exact search.  Terms that start and end in
999
// a forward slash '/' are converted to regular expressions.
1000
export function search_split(
1001
  search: string,
1002
  allowRegexp: boolean = true,
1003
  regexpOptions: string = "i",
1004
): (string | RegExp)[] {
1005
  search = search.trim();
1006
  if (
1007
    allowRegexp &&
1008
    search.length > 2 &&
1009
    search[0] == "/" &&
1010
    search[search.length - 1] == "/"
1011
  ) {
1012
    // in case when entire search is clearly meant to be a regular expression,
1013
    // we directly try for that first.  This is one thing that is documented
1014
    // to work regarding regular expressions, and a search like '/a b/' with
1015
    // whitespace in it would work.  That wouldn't work below unless you explicitly
1016
    // put quotes around it.
1017
    const t = stringOrRegExp(search, regexpOptions);
1018
    if (typeof t != "string") {
1019
      return [t];
1020
    }
1021
  }
1022

1023
  // Now we split on whitespace, allowing for quotes, and get all the search
1024
  // terms and possible regexps.
1025
  const terms: (string | RegExp)[] = [];
1026
  const v = search.split('"');
1027
  const { length } = v;
1028
  for (let i = 0; i < v.length; i++) {
1029
    let element = v[i];
1030
    element = element.trim();
1031
    if (element.length == 0) continue;
1032
    if (i % 2 === 0 || (i === length - 1 && length % 2 === 0)) {
1033
      // The even elements lack quotation
1034
      // if there are an even number of elements that means there is
1035
      // an unclosed quote, so the last element shouldn't be grouped.
1036
      for (const s of split(element)) {
1037
        terms.push(allowRegexp ? stringOrRegExp(s, regexpOptions) : s);
1038
      }
1039
    } else {
1040
      terms.push(
1041
        allowRegexp ? stringOrRegExp(element, regexpOptions) : element,
1042
      );
1043
    }
1044
  }
1045
  return terms;
1046
}
1047

1048
// Convert a string that starts and ends in / to a regexp,
1049
// if it is a VALID regular expression.  Otherwise, returns
1050
// string.
1051
function stringOrRegExp(s: string, options: string): string | RegExp {
1052
  if (s.length < 2 || s[0] != "/" || s[s.length - 1] != "/")
1053
    return s.toLowerCase();
1054
  try {
1055
    return new RegExp(s.slice(1, -1), options);
1056
  } catch (_err) {
1057
    // if there is an error, then we just use the string itself
1058
    // in the search.  We assume anybody using regexp's in a search
1059
    // is reasonably sophisticated, so they don't need hand holding
1060
    // error messages (CodeMirror doesn't give any indication when
1061
    // a regexp is invalid).
1062
    return s.toLowerCase();
1063
  }
1064
}
1065

1066
function isMatch(s: string, x: string | RegExp): boolean {
1067
  if (typeof x == "string") {
1068
    if (x[0] == "-") {
1069
      // negate
1070
      if (x.length == 1) {
1071
        // special case of empty -- no-op, since when you type -foo, you first type "-" and it
1072
        // is disturbing for everything to immediately vanish.
1073
        return true;
1074
      }
1075
      return !isMatch(s, x.slice(1));
1076
    }
1077
    if (x[0] === "#") {
1078
      // only match hashtag at end of word (the \b), so #fo does not match #foo.
1079
      return s.search(new RegExp(x + "\\b")) != -1;
1080
    }
1081
    return s.includes(x);
1082
  } else {
1083
    // regular expression instead of string
1084
    return x.test?.(s);
1085
  }
1086
  return false;
1087
}
1088

1089
// s = lower case string
1090
// v = array of search terms as output by search_split above
1091
export function search_match(s: string, v: (string | RegExp)[]): boolean {
1092
  if (typeof s != "string" || !is_array(v)) {
1093
    // be safe against non Typescript clients
1094
    return false;
1095
  }
1096
  s = s.toLowerCase();
1097
  // we also make a version with no backslashes, since our markdown slate editor does a lot
1098
  // of escaping, e.g., of dashes, and this is confusing when doing searches, e.g., see
1099
  //  https://github.com/sagemathinc/cocalc/issues/6915
1100
  const s1 = s.replace(/\\/g, "");
1101
  for (let x of v) {
1102
    if (!isMatch(s, x) && !isMatch(s1, x)) return false;
1103
  }
1104
  // no term doesn't match, so we have a match.
1105
  return true;
1106
}
1107

1108
export let RUNNING_IN_NODE: boolean;
1109
try {
1110
  RUNNING_IN_NODE = process?.title == "node";
1111
} catch (_err) {
1112
  // error since process probably not defined at all (unless there is a node polyfill).
1113
  RUNNING_IN_NODE = false;
1114
}
1115

1116
/*
1117
The functions to_json_socket and from_json_socket are for sending JSON data back
1118
and forth in serialized form over a socket connection.   They replace Date objects by the
1119
object {DateEpochMS:ms_since_epoch} *only* during transit.   This is much better than
1120
converting to ISO, then using a regexp, since then all kinds of strings will get
1121
converted that were never meant to be date objects at all, e.g., a filename that is
1122
a ISO time string.  Also, ms since epoch is less ambiguous regarding old/different
1123
browsers, and more compact.
1124

1125
If you change SOCKET_DATE_KEY, then all clients and servers and projects must be
1126
simultaneously restarted.  And yes, I perhaps wish I had made this key more obfuscated.
1127
That said, we also check the object length when translating back so only objects
1128
exactly of the form {DateEpochMS:value} get transformed to a date.
1129
*/
1130
const SOCKET_DATE_KEY = "DateEpochMS";
1131

1132
function socket_date_replacer(key: string, value: any): any {
1133
  // @ts-ignore
1134
  const x = this[key];
1135
  return x instanceof Date ? { [SOCKET_DATE_KEY]: x.valueOf() } : value;
1136
}
1137

1138
export function to_json_socket(x: any): string {
1139
  return JSON.stringify(x, socket_date_replacer);
1140
}
1141

1142
function socket_date_parser(_key: string, value: any): any {
1143
  const x = value?.[SOCKET_DATE_KEY];
1144
  return x != null && len(value) == 1 ? new Date(x) : value;
1145
}
1146

1147
export function from_json_socket(x: string): any {
1148
  try {
1149
    return JSON.parse(x, socket_date_parser);
1150
  } catch (err) {
1151
    console.debug(`from_json: error parsing ${x} (=${to_json(x)}) from JSON`);
1152
    throw err;
1153
  }
1154
}
1155

1156
// convert object x to a JSON string, removing any keys that have "pass" in them and
1157
// any values that are potentially big -- this is meant to only be used for logging.
1158
export function to_safe_str(x: any): string {
1159
  if (typeof x === "string") {
1160
    // nothing we can do at this point -- already a string.
1161
    return x;
1162
  }
1163
  const obj = {};
1164
  for (const key in x) {
1165
    let value = x[key];
1166
    let sanitize = false;
1167

1168
    if (
1169
      key.indexOf("pass") !== -1 ||
1170
      key.indexOf("token") !== -1 ||
1171
      key.indexOf("secret") !== -1
1172
    ) {
1173
      sanitize = true;
1174
    } else if (typeof value === "string" && value.slice(0, 7) === "sha512$") {
1175
      sanitize = true;
1176
    }
1177

1178
    if (sanitize) {
1179
      obj[key] = "(unsafe)";
1180
    } else {
1181
      if (typeof value === "object") {
1182
        value = "[object]"; // many objects, e.g., buffers can block for seconds to JSON...
1183
      } else if (typeof value === "string") {
1184
        value = trunc(value, 1000); // long strings are not SAFE -- since JSON'ing them for logging blocks for seconds!
1185
      }
1186
      obj[key] = value;
1187
    }
1188
  }
1189

1190
  return JSON.stringify(obj);
1191
}
1192

1193
// convert from a JSON string to Javascript (properly dealing with ISO dates)
1194
//   e.g.,   2016-12-12T02:12:03.239Z    and    2016-12-12T02:02:53.358752
1195
const reISO =
1196
  /^(\d{4})-(\d{2})-(\d{2})T(\d{2}):(\d{2}):(\d{2}(?:\.\d*))(?:Z|(\+|-)([\d|:]*))?$/;
1197
export function date_parser(_key: string | undefined, value: any) {
1198
  if (typeof value === "string" && value.length >= 20 && reISO.exec(value)) {
1199
    return ISO_to_Date(value);
1200
  } else {
1201
    return value;
1202
  }
1203
}
1204

1205
export function ISO_to_Date(s: string): Date {
1206
  if (s.indexOf("Z") === -1) {
1207
    // Firefox assumes local time rather than UTC if there is no Z.   However,
1208
    // our backend might possibly send a timestamp with no Z and it should be
1209
    // interpretted as UTC anyways.
1210
    // That said, with the to_json_socket/from_json_socket code, the browser
1211
    // shouldn't be running this parser anyways.
1212
    // In particular: TODO -- completely get rid of using this in from_json... if possible!
1213
    s += "Z";
1214
  }
1215
  return new Date(s);
1216
}
1217

1218
export function from_json(x: string): any {
1219
  try {
1220
    return JSON.parse(x, date_parser);
1221
  } catch (err) {
1222
    console.debug(`from_json: error parsing ${x} (=${to_json(x)}) from JSON`);
1223
    throw err;
1224
  }
1225
}
1226

1227
// Returns modified version of obj with any string
1228
// that look like ISO dates to actual Date objects.  This mutates
1229
// obj in place as part of the process.
1230
// date_keys = 'all' or list of keys in nested object whose values
1231
// should be considered.  Nothing else is considered!
1232
export function fix_json_dates(obj: any, date_keys?: "all" | string[]) {
1233
  if (date_keys == null) {
1234
    // nothing to do
1235
    return obj;
1236
  }
1237
  if (is_object(obj)) {
1238
    for (let k in obj) {
1239
      const v = obj[k];
1240
      if (typeof v === "object") {
1241
        fix_json_dates(v, date_keys);
1242
      } else if (
1243
        typeof v === "string" &&
1244
        v.length >= 20 &&
1245
        reISO.exec(v) &&
1246
        (date_keys === "all" || Array.from(date_keys).includes(k))
1247
      ) {
1248
        obj[k] = new Date(v);
1249
      }
1250
    }
1251
  } else if (is_array(obj)) {
1252
    for (let i in obj) {
1253
      const x = obj[i];
1254
      obj[i] = fix_json_dates(x, date_keys);
1255
    }
1256
  } else if (
1257
    typeof obj === "string" &&
1258
    obj.length >= 20 &&
1259
    reISO.exec(obj) &&
1260
    date_keys === "all"
1261
  ) {
1262
    return new Date(obj);
1263
  }
1264
  return obj;
1265
}
1266

1267
// converts a Date object to an ISO string in UTC.
1268
// NOTE -- we remove the +0000 (or whatever) timezone offset, since *all* machines within
1269
// the CoCalc servers are assumed to be on UTC.
1270
function to_iso(d: Date): string {
1271
  return new Date(d.valueOf() - d.getTimezoneOffset() * 60 * 1000)
1272
    .toISOString()
1273
    .slice(0, -5);
1274
}
1275

1276
// turns a Date object into a more human readable more friendly directory name in the local timezone
1277
export function to_iso_path(d: Date): string {
1278
  return to_iso(d).replace("T", "-").replace(/:/g, "");
1279
}
1280

1281
// does the given object (first arg) have the given key (second arg)?
1282
export const has_key: (obj: object, path: string[] | string) => boolean =
1283
  lodash.has;
1284

1285
// returns the values of a map
1286
export const values = lodash.values;
1287

1288
// as in python, makes a map from an array of pairs [(x,y),(z,w)] --> {x:y, z:w}
1289
export function dict(v: [string, any][]): { [key: string]: any } {
1290
  const obj: { [key: string]: any } = {};
1291
  for (let a of Array.from(v)) {
1292
    if (a.length !== 2) {
1293
      throw new Error("ValueError: unexpected length of tuple");
1294
    }
1295
    obj[a[0]] = a[1];
1296
  }
1297
  return obj;
1298
}
1299

1300
// remove first occurrence of value (just like in python);
1301
// throws an exception if val not in list.
1302
// mutates arr.
1303
export function remove(arr: any[], val: any): void {
1304
  for (
1305
    let i = 0, end = arr.length, asc = 0 <= end;
1306
    asc ? i < end : i > end;
1307
    asc ? i++ : i--
1308
  ) {
1309
    if (arr[i] === val) {
1310
      arr.splice(i, 1);
1311
      return;
1312
    }
1313
  }
1314
  throw new Error("ValueError -- item not in array");
1315
}
1316

1317
export const max: (x: any[]) => any = lodash.max;
1318
export const min: (x: any[]) => any = lodash.min;
1319

1320
// Takes a path string and file name and gives the full path to the file
1321
export function path_to_file(path: string = "", file: string): string {
1322
  if (path === "") {
1323
    return file;
1324
  }
1325
  return path + "/" + file;
1326
}
1327

1328
// Given a path of the form foo/bar/.baz.ext.something returns foo/bar/baz.ext.
1329
// For example:
1330
//    .example.ipynb.sage-jupyter --> example.ipynb
1331
//    tmp/.example.ipynb.sage-jupyter --> tmp/example.ipynb
1332
//    .foo.txt.sage-chat --> foo.txt
1333
//    tmp/.foo.txt.sage-chat --> tmp/foo.txt
1334

1335
export function original_path(path: string): string {
1336
  const s = path_split(path);
1337
  if (s.tail[0] != "." || s.tail.indexOf(".sage-") == -1) {
1338
    return path;
1339
  }
1340
  const ext = filename_extension(s.tail);
1341
  let x = s.tail.slice(
1342
    s.tail[0] === "." ? 1 : 0,
1343
    s.tail.length - (ext.length + 1),
1344
  );
1345
  if (s.head !== "") {
1346
    x = s.head + "/" + x;
1347
  }
1348
  return x;
1349
}
1350

1351
export function lower_email_address(email_address: any): string {
1352
  if (email_address == null) {
1353
    return "";
1354
  }
1355
  if (typeof email_address !== "string") {
1356
    // silly, but we assume it is a string, and I'm concerned
1357
    // about an attack involving badly formed messages
1358
    email_address = JSON.stringify(email_address);
1359
  }
1360
  // make email address lower case
1361
  return email_address.toLowerCase();
1362
}
1363

1364
// Parses a string representing a search of users by email or non-email
1365
// Expects the string to be delimited by commas or semicolons
1366
// between multiple users
1367
//
1368
// Non-email strings are ones without an '@' and will be split on whitespace
1369
//
1370
// Emails may be wrapped by angle brackets.
1371
//   ie. <[email protected]> is valid and understood as [email protected]
1372
//   (Note that <<[email protected]> will be <[email protected] which is not valid)
1373
// Emails must be legal as specified by RFC822
1374
//
1375
// returns an object with the queries in lowercase
1376
// eg.
1377
// {
1378
//    string_queries: [["firstname", "lastname"], ["somestring"]]
1379
//    email_queries: ["[email protected]", "[email protected]"]
1380
// }
1381
export function parse_user_search(query: string): {
1382
  string_queries: string[][];
1383
  email_queries: string[];
1384
} {
1385
  const r = { string_queries: [] as string[][], email_queries: [] as string[] };
1386
  if (typeof query !== "string") {
1387
    // robustness against bad input from non-TS client.
1388
    return r;
1389
  }
1390
  const queries = query
1391
    .split("\n")
1392
    .map((q1) => q1.split(/,|;/))
1393
    .reduce((acc, val) => acc.concat(val), []) // flatten
1394
    .map((q) => q.trim().toLowerCase());
1395
  const email_re = /<(.*)>/;
1396
  for (const x of queries) {
1397
    if (x) {
1398
      if (x.indexOf("@") === -1 || x.startsWith("@")) {
1399
        // Is obviously not an email, e.g., no @ or starts with @ = username, e.g., @wstein.
1400
        r.string_queries.push(x.split(/\s+/g));
1401
      } else {
1402
        // Might be an email address:
1403
        // extract just the email address out
1404
        for (let a of split(x)) {
1405
          // Ensures that we don't throw away emails like
1406
          // "<validEmail>"[email protected]
1407
          if (a[0] === "<") {
1408
            const match = email_re.exec(a);
1409
            a = match != null ? match[1] : a;
1410
          }
1411
          if (is_valid_email_address(a)) {
1412
            r.email_queries.push(a);
1413
          }
1414
        }
1415
      }
1416
    }
1417
  }
1418
  return r;
1419
}
1420

1421
// Delete trailing whitespace in the string s.
1422
export function delete_trailing_whitespace(s: string): string {
1423
  return s.replace(/[^\S\n]+$/gm, "");
1424
}
1425

1426
export function retry_until_success(opts: {
1427
  f: Function;
1428
  start_delay?: number;
1429
  max_delay?: number;
1430
  factor?: number;
1431
  max_tries?: number;
1432
  max_time?: number;
1433
  log?: Function;
1434
  warn?: Function;
1435
  name?: string;
1436
  cb?: Function;
1437
}): void {
1438
  let start_time;
1439
  opts = defaults(opts, {
1440
    f: required, // f((err) => )
1441
    start_delay: 100, // milliseconds
1442
    max_delay: 20000, // milliseconds -- stop increasing time at this point
1443
    factor: 1.4, // multiply delay by this each time
1444
    max_tries: undefined, // maximum number of times to call f
1445
    max_time: undefined, // milliseconds -- don't call f again if the call would start after this much time from first call
1446
    log: undefined,
1447
    warn: undefined,
1448
    name: "",
1449
    cb: undefined, // called with cb() on *success*; cb(error, last_error) if max_tries is exceeded
1450
  });
1451
  let delta = opts.start_delay as number;
1452
  let tries = 0;
1453
  if (opts.max_time != null) {
1454
    start_time = new Date();
1455
  }
1456
  const g = function () {
1457
    tries += 1;
1458
    if (opts.log != null) {
1459
      if (opts.max_tries != null) {
1460
        opts.log(
1461
          `retry_until_success(${opts.name}) -- try ${tries}/${opts.max_tries}`,
1462
        );
1463
      }
1464
      if (opts.max_time != null) {
1465
        opts.log(
1466
          `retry_until_success(${opts.name}) -- try ${tries} (started ${
1467
            Date.now() - start_time
1468
          }ms ago; will stop before ${opts.max_time}ms max time)`,
1469
        );
1470
      }
1471
      if (opts.max_tries == null && opts.max_time == null) {
1472
        opts.log(`retry_until_success(${opts.name}) -- try ${tries}`);
1473
      }
1474
    }
1475
    opts.f(function (err) {
1476
      if (err) {
1477
        if (err === "not_public") {
1478
          opts.cb?.("not_public");
1479
          return;
1480
        }
1481
        if (err && opts.warn != null) {
1482
          opts.warn(`retry_until_success(${opts.name}) -- err=${err}`);
1483
        }
1484
        if (opts.log != null) {
1485
          opts.log(`retry_until_success(${opts.name}) -- err=${err}`);
1486
        }
1487
        if (opts.max_tries != null && opts.max_tries <= tries) {
1488
          opts.cb?.(
1489
            `maximum tries (=${opts.max_tries}) exceeded - last error ${err}`,
1490
            err,
1491
          );
1492
          return;
1493
        }
1494
        delta = Math.min(
1495
          opts.max_delay as number,
1496
          (opts.factor as number) * delta,
1497
        );
1498
        if (
1499
          opts.max_time != null &&
1500
          Date.now() - start_time + delta > opts.max_time
1501
        ) {
1502
          opts.cb?.(
1503
            `maximum time (=${opts.max_time}ms) exceeded - last error ${err}`,
1504
            err,
1505
          );
1506
          return;
1507
        }
1508
        return setTimeout(g, delta);
1509
      } else {
1510
        if (opts.log != null) {
1511
          opts.log(`retry_until_success(${opts.name}) -- success`);
1512
        }
1513
        opts.cb?.();
1514
      }
1515
    });
1516
  };
1517
  g();
1518
}
1519

1520
// Class to use for mapping a collection of strings to characters (e.g., for use with diff/patch/match).
1521
export class StringCharMapping {
1522
  private _to_char: { [s: string]: string } = {};
1523
  private _next_char: string = "A";
1524
  public _to_string: { [s: string]: string } = {}; // yes, this is publicly accessed (TODO: fix)
1525

1526
  constructor(opts?) {
1527
    let ch, st;
1528
    this.find_next_char = this.find_next_char.bind(this);
1529
    this.to_string = this.to_string.bind(this);
1530
    this.to_array = this.to_array.bind(this);
1531
    if (opts == null) {
1532
      opts = {};
1533
    }
1534
    opts = defaults(opts, {
1535
      to_char: undefined,
1536
      to_string: undefined,
1537
    });
1538
    if (opts.to_string != null) {
1539
      for (ch in opts.to_string) {
1540
        st = opts.to_string[ch];
1541
        this._to_string[ch] = st;
1542
        this._to_char[st] = ch;
1543
      }
1544
    }
1545
    if (opts.to_char != null) {
1546
      for (st in opts.to_char) {
1547
        ch = opts.to_char[st];
1548
        this._to_string[ch] = st;
1549
        this._to_char[st] = ch;
1550
      }
1551
    }
1552
    this.find_next_char();
1553
  }
1554

1555
  private find_next_char(): void {
1556
    while (true) {
1557
      this._next_char = String.fromCharCode(this._next_char.charCodeAt(0) + 1);
1558
      if (this._to_string[this._next_char] == null) {
1559
        // found it!
1560
        break;
1561
      }
1562
    }
1563
  }
1564

1565
  public to_string(strings: string[]): string {
1566
    let t = "";
1567
    for (const s of strings) {
1568
      const a = this._to_char[s];
1569
      if (a != null) {
1570
        t += a;
1571
      } else {
1572
        t += this._next_char;
1573
        this._to_char[s] = this._next_char;
1574
        this._to_string[this._next_char] = s;
1575
        this.find_next_char();
1576
      }
1577
    }
1578
    return t;
1579
  }
1580

1581
  public to_array(x: string): string[] {
1582
    return Array.from(x).map((s) => this.to_string[s]);
1583
  }
1584

1585
  // for testing
1586
  public _debug_get_to_char() {
1587
    return this._to_char;
1588
  }
1589
  public _debug_get_next_char() {
1590
    return this._next_char;
1591
  }
1592
}
1593

1594
// Used in the database, etc., for different types of users of a project
1595
export const PROJECT_GROUPS: string[] = [
1596
  "owner",
1597
  "collaborator",
1598
  "viewer",
1599
  "invited_collaborator",
1600
  "invited_viewer",
1601
];
1602

1603
// format is 2014-04-04-061502
1604
export function parse_bup_timestamp(s: string): Date {
1605
  const v = [
1606
    s.slice(0, 4),
1607
    s.slice(5, 7),
1608
    s.slice(8, 10),
1609
    s.slice(11, 13),
1610
    s.slice(13, 15),
1611
    s.slice(15, 17),
1612
    "0",
1613
  ];
1614
  return new Date(`${v[1]}/${v[2]}/${v[0]} ${v[3]}:${v[4]}:${v[5]} UTC`);
1615
}
1616

1617
// NOTE: this hash works, but the crypto hashes in nodejs, eg.,
1618
// sha1 (as used here packages/backend/sha1.ts) are MUCH faster
1619
// for large strings.  If there is some way to switch to one of those,
1620
// it would be better, but we have to worry about how this is already deployed
1621
// e.g., hashes in the database.
1622
export function hash_string(s: string): number {
1623
  if (typeof s != "string") {
1624
    return 0; // just in case non-typescript code tries to use this
1625
  }
1626
  // see http://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript-jquery
1627
  let hash = 0;
1628
  if (s.length === 0) {
1629
    return hash;
1630
  }
1631
  const n = s.length;
1632
  for (let i = 0; i < n; i++) {
1633
    const chr = s.charCodeAt(i);
1634
    hash = (hash << 5) - hash + chr;
1635
    hash |= 0; // convert to 32-bit integer
1636
  }
1637
  return hash;
1638
}
1639

1640
export function parse_hashtags(t?: string): [number, number][] {
1641
  // return list of pairs (i,j) such that t.slice(i,j) is a hashtag (starting with #).
1642
  const v: [number, number][] = [];
1643
  if (typeof t != "string") {
1644
    // in case of non-Typescript user
1645
    return v;
1646
  }
1647
  let base = 0;
1648
  while (true) {
1649
    let i: number = t.indexOf("#");
1650
    if (i === -1 || i === t.length - 1) {
1651
      return v;
1652
    }
1653
    base += i + 1;
1654
    if (t[i + 1] === "#" || !(i === 0 || t[i - 1].match(/\s/))) {
1655
      t = t.slice(i + 1);
1656
      continue;
1657
    }
1658
    t = t.slice(i + 1);
1659
    // find next whitespace or non-alphanumeric or dash
1660
    // TODO: this lines means hashtags must be US ASCII --
1661
    //    see http://stackoverflow.com/questions/1661197/valid-characters-for-javascript-variable-names
1662
    const m = t.match(/\s|[^A-Za-z0-9_\-]/);
1663
    if (m && m.index != null) {
1664
      i = m.index;
1665
    } else {
1666
      i = -1;
1667
    }
1668
    if (i === 0) {
1669
      // hash followed immediately by whitespace -- markdown desc
1670
      base += i + 1;
1671
      t = t.slice(i + 1);
1672
    } else {
1673
      // a hash tag
1674
      if (i === -1) {
1675
        // to the end
1676
        v.push([base - 1, base + t.length]);
1677
        return v;
1678
      } else {
1679
        v.push([base - 1, base + i]);
1680
        base += i + 1;
1681
        t = t.slice(i + 1);
1682
      }
1683
    }
1684
  }
1685
}
1686

1687
// Return true if (1) path is contained in one
1688
// of the given paths (a list of strings) -- or path without
1689
// zip extension is in paths.
1690
// Always returns false if path is undefined/null (since
1691
// that might be dangerous, right)?
1692
export function path_is_in_public_paths(
1693
  path: string | undefined | null,
1694
  paths: string[] | Set<string> | object | undefined | null,
1695
): boolean {
1696
  return containing_public_path(path, paths) != null;
1697
}
1698

1699
// returns a string in paths if path is public because of that string
1700
// Otherwise, returns undefined.
1701
// IMPORTANT: a possible returned string is "", which is falsey but defined!
1702
// paths can be an array or object (with keys the paths) or a Set
1703
export function containing_public_path(
1704
  path: string | undefined | null,
1705
  paths: string[] | Set<string> | object | undefined | null,
1706
): undefined | string {
1707
  if (paths == null || path == null) {
1708
    // just in case of non-typescript clients
1709
    return;
1710
  }
1711
  if (path.indexOf("../") !== -1) {
1712
    // just deny any potentially trickiery involving relative
1713
    // path segments (TODO: maybe too restrictive?)
1714
    return;
1715
  }
1716
  if (is_array(paths) || is_set(paths)) {
1717
    // array so "of"
1718
    // @ts-ignore
1719
    for (const p of paths) {
1720
      if (p == null) continue; // the typescript typings evidently aren't always exactly right
1721
      if (p === "") {
1722
        // the whole project is public, which matches everything
1723
        return "";
1724
      }
1725
      if (path === p) {
1726
        // exact match
1727
        return p;
1728
      }
1729
      if (path.slice(0, p.length + 1) === p + "/") {
1730
        return p;
1731
      }
1732
    }
1733
  } else if (is_object(paths)) {
1734
    for (const p in paths) {
1735
      // object and want keys, so *of*
1736
      if (p === "") {
1737
        // the whole project is public, which matches everything
1738
        return "";
1739
      }
1740
      if (path === p) {
1741
        // exact match
1742
        return p;
1743
      }
1744
      if (path.slice(0, p.length + 1) === p + "/") {
1745
        return p;
1746
      }
1747
    }
1748
  } else {
1749
    throw Error("paths must be undefined, an array, or a map");
1750
  }
1751
  if (filename_extension(path) === "zip") {
1752
    // is path something_public.zip ?
1753
    return containing_public_path(path.slice(0, path.length - 4), paths);
1754
  }
1755
  return undefined;
1756
}
1757

1758
export const is_equal = lodash.isEqual;
1759

1760
export function is_whitespace(s?: string): boolean {
1761
  return (s?.trim().length ?? 0) == 0;
1762
}
1763

1764
export function lstrip(s: string): string {
1765
  return s.replace(/^\s*/g, "");
1766
}
1767

1768
export function date_to_snapshot_format(
1769
  d: Date | undefined | null | number,
1770
): string {
1771
  if (d == null) {
1772
    d = 0;
1773
  }
1774
  if (typeof d === "number") {
1775
    d = new Date(d);
1776
  }
1777
  let s = d.toJSON();
1778
  s = s.replace("T", "-").replace(/:/g, "");
1779
  const i = s.lastIndexOf(".");
1780
  return s.slice(0, i);
1781
}
1782

1783
export function stripeDate(d: number): string {
1784
  // https://github.com/sagemathinc/cocalc/issues/3254
1785
  // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Intl#Locale_negotiation
1786
  return new Date(d * 1000).toLocaleDateString(undefined, {
1787
    year: "numeric",
1788
    month: "long",
1789
    day: "numeric",
1790
  });
1791
}
1792

1793
export function to_money(n: number, d = 2): string {
1794
  // see http://stackoverflow.com/questions/149055/how-can-i-format-numbers-as-money-in-javascript
1795
  // TODO: replace by using react-intl...
1796
  return n.toFixed(d).replace(/(\d)(?=(\d{3})+\.)/g, "$1,");
1797
}
1798

1799
// numbers with commas -- https://stackoverflow.com/questions/2901102/how-to-format-a-number-with-commas-as-thousands-separators
1800
export function commas(n: number): string {
1801
  if (n == null) {
1802
    // in case of bugs, at least fail with empty in prod
1803
    return "";
1804
  }
1805
  return n.toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",");
1806
}
1807

1808
// Display currency with a dollar sign, rounded to *nearest*.
1809
// If d is not given and n is less than 1 cent, will show 3 digits
1810
// instead of 2.
1811
export function currency(n: number, d?: number) {
1812
  if (n == 0) {
1813
    return `$0.00`;
1814
  }
1815
  let s = `$${to_money(Math.abs(n) ?? 0, d ?? (Math.abs(n) < 0.0095 ? 3 : 2))}`;
1816
  if (n < 0) {
1817
    s = `-${s}`;
1818
  }
1819
  if (d == null || d <= 2) {
1820
    return s;
1821
  }
1822
  // strip excessive 0's off the end
1823
  const i = s.indexOf(".");
1824
  while (s[s.length - 1] == "0" && i <= s.length - (d ?? 2)) {
1825
    s = s.slice(0, s.length - 1);
1826
  }
1827
  return s;
1828
}
1829

1830
export function stripeAmount(
1831
  unitPrice: number,
1832
  currency: string,
1833
  units = 1,
1834
): string {
1835
  // input is in pennies
1836
  if (currency !== "usd") {
1837
    // TODO: need to make this look nice with symbols for other currencies...
1838
    return `${currency == "eur" ? "€" : ""}${to_money(
1839
      (units * unitPrice) / 100,
1840
    )} ${currency.toUpperCase()}`;
1841
  }
1842
  return `$${to_money((units * unitPrice) / 100)} USD`;
1843
}
1844

1845
export function planInterval(
1846
  interval: string,
1847
  interval_count: number = 1,
1848
): string {
1849
  return `${interval_count} ${plural(interval_count, interval)}`;
1850
}
1851

1852
// get a subarray of all values between the two given values inclusive,
1853
// provided in either order
1854
export function get_array_range(arr: any[], value1: any, value2: any): any[] {
1855
  let index1 = arr.indexOf(value1);
1856
  let index2 = arr.indexOf(value2);
1857
  if (index1 > index2) {
1858
    [index1, index2] = [index2, index1];
1859
  }
1860
  return arr.slice(index1, +index2 + 1 || undefined);
1861
}
1862

1863
function seconds2hms_days(
1864
  d: number,
1865
  h: number,
1866
  m: number,
1867
  longform: boolean,
1868
): string {
1869
  h = h % 24;
1870
  const s = h * 60 * 60 + m * 60;
1871
  const x = s > 0 ? seconds2hms(s, longform, false) : "";
1872
  if (longform) {
1873
    return `${d} ${plural(d, "day")} ${x}`.trim();
1874
  } else {
1875
    return `${d}d${x}`;
1876
  }
1877
}
1878

1879
// like seconds2hms, but only up to minute-resultion
1880
export function seconds2hm(secs: number, longform: boolean = false): string {
1881
  return seconds2hms(secs, longform, false);
1882
}
1883

1884
// dear future developer: look into test/misc-test.coffee to see how the expected output is defined.
1885
export function seconds2hms(
1886
  secs: number,
1887
  longform: boolean = false,
1888
  show_seconds: boolean = true,
1889
): string {
1890
  let s;
1891
  if (!longform && secs < 10) {
1892
    s = round2(secs % 60);
1893
  } else if (!longform && secs < 60) {
1894
    s = round1(secs % 60);
1895
  } else {
1896
    s = Math.round(secs % 60);
1897
  }
1898
  const m = Math.floor(secs / 60) % 60;
1899
  const h = Math.floor(secs / 60 / 60);
1900
  const d = Math.floor(secs / 60 / 60 / 24);
1901
  // for more than one day, special routine (ignoring seconds altogether)
1902
  if (d > 0) {
1903
    return seconds2hms_days(d, h, m, longform);
1904
  }
1905
  if (h === 0 && m === 0 && show_seconds) {
1906
    if (longform) {
1907
      return `${s} ${plural(s, "second")}`;
1908
    } else {
1909
      return `${s}s`;
1910
    }
1911
  }
1912
  if (h > 0) {
1913
    if (longform) {
1914
      let ret = `${h} ${plural(h, "hour")}`;
1915
      if (m > 0) {
1916
        ret += ` ${m} ${plural(m, "minute")}`;
1917
      }
1918
      return ret;
1919
    } else {
1920
      if (show_seconds) {
1921
        return `${h}h${m}m${s}s`;
1922
      } else {
1923
        return `${h}h${m}m`;
1924
      }
1925
    }
1926
  }
1927
  if (m > 0 || !show_seconds) {
1928
    if (show_seconds) {
1929
      if (longform) {
1930
        let ret = `${m} ${plural(m, "minute")}`;
1931
        if (s > 0) {
1932
          ret += ` ${s} ${plural(s, "second")}`;
1933
        }
1934
        return ret;
1935
      } else {
1936
        return `${m}m${s}s`;
1937
      }
1938
    } else {
1939
      if (longform) {
1940
        return `${m} ${plural(m, "minute")}`;
1941
      } else {
1942
        return `${m}m`;
1943
      }
1944
    }
1945
  }
1946
  return "";
1947
}
1948

1949
export function range(n: number): number[] {
1950
  const v: number[] = [];
1951
  for (let i = 0; i < n; i++) {
1952
    v.push(i);
1953
  }
1954
  return v;
1955
}
1956

1957
// Like Python's enumerate
1958
export function enumerate(v: any[]) {
1959
  const w: [number, any][] = [];
1960
  let i = 0;
1961
  for (let x of Array.from(v)) {
1962
    w.push([i, x]);
1963
    i += 1;
1964
  }
1965
  return w;
1966
}
1967

1968
// converts an array to a "human readable" array
1969
export function to_human_list(arr: any[]): string {
1970
  arr = lodash.map(arr, (x) => `${x}`);
1971
  if (arr.length > 1) {
1972
    return arr.slice(0, -1).join(", ") + " and " + arr.slice(-1);
1973
  } else if (arr.length === 1) {
1974
    return arr[0].toString();
1975
  } else {
1976
    return "";
1977
  }
1978
}
1979

1980
// derive the console initialization filename from the console's filename
1981
// used in webapp and console_server_child
1982
export function console_init_filename(path: string): string {
1983
  const x = path_split(path);
1984
  x.tail = `.${x.tail}.init`;
1985
  if (x.head === "") {
1986
    return x.tail;
1987
  }
1988
  return [x.head, x.tail].join("/");
1989
}
1990

1991
export function has_null_leaf(obj: object): boolean {
1992
  for (const k in obj) {
1993
    const v = obj[k];
1994
    if (v === null || (typeof v === "object" && has_null_leaf(v))) {
1995
      return true;
1996
    }
1997
  }
1998
  return false;
1999
}
2000

2001
// mutate obj and delete any undefined leafs.
2002
// was used for MsgPack -- but the ignoreUndefined:true option
2003
// to the encoder is a much better fix.
2004
// export function removeUndefinedLeafs(obj: object) {
2005
//   for (const k in obj) {
2006
//     const v = obj[k];
2007
//     if (v === undefined) {
2008
//       delete obj[k];
2009
//     } else if (is_object(v)) {
2010
//       removeUndefinedLeafs(v);
2011
//     }
2012
//   }
2013
// }
2014

2015
// Peer Grading
2016
// This function takes a list of student_ids,
2017
// and a number N of the desired number of peers per student.
2018
// It returns an object, mapping each student to a list of N peers.
2019
export function peer_grading(
2020
  students: string[],
2021
  N: number = 2,
2022
): { [student_id: string]: string[] } {
2023
  if (N <= 0) {
2024
    throw Error("Number of peer assigments must be at least 1");
2025
  }
2026
  if (students.length <= N) {
2027
    throw Error(`You need at least ${N + 1} students`);
2028
  }
2029

2030
  const assignment: { [student_id: string]: string[] } = {};
2031

2032
  // make output dict keys sorted like students input array
2033
  for (const s of students) {
2034
    assignment[s] = [];
2035
  }
2036

2037
  // randomize peer assignments
2038
  const s_random = lodash.shuffle(students);
2039

2040
  // the peer grading groups are set here. Think of nodes in
2041
  // a circular graph, and node i is associated with grading
2042
  // nodes i+1 up to i+N.
2043
  const L = students.length;
2044
  for (let i = 0; i < L; i++) {
2045
    for (let j = i + 1; j <= i + N; j++) {
2046
      assignment[s_random[i]].push(s_random[j % L]);
2047
    }
2048
  }
2049

2050
  // sort each peer group by the order of the `student` input list
2051
  for (let k in assignment) {
2052
    const v = assignment[k];
2053
    assignment[k] = lodash.sortBy(v, (s) => students.indexOf(s));
2054
  }
2055
  return assignment;
2056
}
2057

2058
// Checks if the string only makes sense (heuristically) as downloadable url
2059
export function is_only_downloadable(s: string): boolean {
2060
  return s.indexOf("://") !== -1 || startswith(s, "[email protected]");
2061
}
2062

2063
export function ensure_bound(x: number, min: number, max: number): number {
2064
  return x < min ? min : x > max ? max : x;
2065
}
2066

2067
export const EDITOR_PREFIX = "editor-";
2068

2069
// convert a file path to the "name" of the underlying editor tab.
2070
// needed because otherwise filenames like 'log' would cause problems
2071
export function path_to_tab(name: string): string {
2072
  return `${EDITOR_PREFIX}${name}`;
2073
}
2074

2075
// assumes a valid editor tab name...
2076
// If invalid or undefined, returns undefined
2077
export function tab_to_path(name?: string): string | undefined {
2078
  if (name?.substring(0, 7) === EDITOR_PREFIX) {
2079
    return name.substring(7);
2080
  }
2081
  return;
2082
}
2083

2084
// suggest a new filename when duplicating it as follows:
2085
// strip extension, split at '_' or '-' if it exists
2086
// try to parse a number, if it works, increment it, etc.
2087
// Handle leading zeros for the number (see https://github.com/sagemathinc/cocalc/issues/2973)
2088
export function suggest_duplicate_filename(name: string): string {
2089
  let ext;
2090
  ({ name, ext } = separate_file_extension(name));
2091
  const idx_dash = name.lastIndexOf("-");
2092
  const idx_under = name.lastIndexOf("_");
2093
  const idx = Math.max(idx_dash, idx_under);
2094
  let new_name: string | undefined = undefined;
2095
  if (idx > 0) {
2096
    const [prefix, ending] = Array.from([
2097
      name.slice(0, idx + 1),
2098
      name.slice(idx + 1),
2099
    ]);
2100
    // Pad the number with leading zeros to maintain the original length
2101
    const paddedEnding = ending.padStart(ending.length, "0");
2102
    const num = parseInt(paddedEnding);
2103
    if (!Number.isNaN(num)) {
2104
      // Increment the number and pad it back to the original length
2105
      const newNum = (num + 1).toString().padStart(ending.length, "0");
2106
      new_name = `${prefix}${newNum}`;
2107
    }
2108
  }
2109
  if (new_name == null) {
2110
    new_name = `${name}-1`;
2111
  }
2112
  if (ext.length > 0) {
2113
    new_name += "." + ext;
2114
  }
2115
  return new_name;
2116
}
2117

2118
// Takes an object representing a directed graph shaped as follows:
2119
// DAG =
2120
//     node1 : []
2121
//     node2 : ["node1"]
2122
//     node3 : ["node1", "node2"]
2123
//
2124
// Which represents the following graph:
2125
//   node1 ----> node2
2126
//     |           |
2127
//    \|/          |
2128
//   node3 <-------|
2129
//
2130
// Returns a topological ordering of the DAG
2131
//     object = ["node1", "node2", "node3"]
2132
//
2133
// Throws an error if cyclic
2134
// Runs in O(N + E) where N is the number of nodes and E the number of edges
2135
// Kahn, Arthur B. (1962), "Topological sorting of large networks", Communications of the ACM
2136
export function top_sort(
2137
  DAG: { [node: string]: string[] },
2138
  opts: { omit_sources?: boolean } = { omit_sources: false },
2139
): string[] {
2140
  const { omit_sources } = opts;
2141
  const source_names: string[] = [];
2142
  let num_edges = 0;
2143
  const graph_nodes = {};
2144

2145
  // Ready the nodes for top sort
2146
  for (const name in DAG) {
2147
    const parents = DAG[name];
2148
    if (graph_nodes[name] == null) {
2149
      graph_nodes[name] = {};
2150
    }
2151
    const node = graph_nodes[name];
2152
    node.name = name;
2153
    if (node.children == null) {
2154
      node.children = [];
2155
    }
2156
    node.parent_set = {};
2157
    for (const parent_name of parents) {
2158
      // include element in "parent_set" (see https://github.com/sagemathinc/cocalc/issues/1710)
2159
      node.parent_set[parent_name] = true;
2160
      if (graph_nodes[parent_name] == null) {
2161
        graph_nodes[parent_name] = {};
2162
        // Cover implicit nodes which are assumed to be source nodes
2163
        if (DAG[parent_name] == null) {
2164
          source_names.push(parent_name);
2165
        }
2166
      }
2167
      if (graph_nodes[parent_name].children == null) {
2168
        graph_nodes[parent_name].children = [];
2169
      }
2170

2171
      graph_nodes[parent_name].children.push(node);
2172
    }
2173

2174
    if (parents.length === 0) {
2175
      source_names.push(name);
2176
    } else {
2177
      num_edges += parents.length;
2178
    }
2179
  }
2180

2181
  // Top sort! Non-recursive method since recursion is way slow in javascript
2182
  // https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
2183
  const path: string[] = [];
2184
  const num_sources = source_names.length;
2185
  let walked_edges = 0;
2186

2187
  while (source_names.length !== 0) {
2188
    const curr_name = source_names.shift();
2189
    if (curr_name == null) throw Error("BUG -- can't happen"); // TS :-)
2190
    path.push(curr_name);
2191

2192
    for (const child of graph_nodes[curr_name].children) {
2193
      delete child.parent_set[curr_name];
2194
      walked_edges++;
2195
      if (Object.keys(child.parent_set).length === 0) {
2196
        source_names.push(child.name);
2197
      }
2198
    }
2199
  }
2200

2201
  // Detect lack of sources
2202
  if (num_sources === 0) {
2203
    throw new Error("No sources were detected");
2204
  }
2205

2206
  // Detect cycles
2207
  if (num_edges !== walked_edges) {
2208
    /*// uncomment this when debugging problems.
2209
    if (typeof window != "undefined") {
2210
      (window as any)._DAG = DAG;
2211
    } // so it's possible to debug in browser
2212
    */
2213
    throw new Error("Store has a cycle in its computed values");
2214
  }
2215

2216
  if (omit_sources) {
2217
    return path.slice(num_sources);
2218
  } else {
2219
    return path;
2220
  }
2221
}
2222

2223
// Takes an object obj with keys and values where
2224
// the values are functions and keys are the names
2225
// of the functions.
2226
// Dependency graph is created from the property
2227
// `dependency_names` found on the values
2228
// Returns an object shaped
2229
// DAG =
2230
//     func_name1 : []
2231
//     func_name2 : ["func_name1"]
2232
//     func_name3 : ["func_name1", "func_name2"]
2233
//
2234
// Which represents the following graph:
2235
//   func_name1 ----> func_name2
2236
//     |                |
2237
//    \|/               |
2238
//   func_name3 <-------|
2239
export function create_dependency_graph(obj: {
2240
  [name: string]: Function & { dependency_names?: string[] };
2241
}): { [name: string]: string[] } {
2242
  const DAG = {};
2243
  for (const name in obj) {
2244
    const written_func = obj[name];
2245
    DAG[name] = written_func.dependency_names ?? [];
2246
  }
2247
  return DAG;
2248
}
2249

2250
// modify obj in place substituting as specified in subs recursively,
2251
// both for keys *and* values of obj.  E.g.,
2252
//  obj ={a:{b:'d',d:5}};   obj_key_subs(obj, {d:'x'})
2253
// then obj --> {a:{b:'x',x:5}}.
2254
// This is actually used in user queries to replace {account_id}, {project_id},
2255
// and {now}, but special strings or the time in queries.
2256
export function obj_key_subs(obj: object, subs: { [key: string]: any }): void {
2257
  for (const k in obj) {
2258
    const v = obj[k];
2259
    const s: any = subs[k];
2260
    if (typeof s == "string") {
2261
      // key substitution for strings
2262
      delete obj[k];
2263
      obj[s] = v;
2264
    }
2265
    if (typeof v === "object") {
2266
      obj_key_subs(v, subs);
2267
    } else if (typeof v === "string") {
2268
      // value substitution
2269
      const s2: any = subs[v];
2270
      if (s2 != null) {
2271
        obj[k] = s2;
2272
      }
2273
    }
2274
  }
2275
}
2276

2277
// this is a helper for sanitizing html. It is used in
2278
// * packages/backend/misc_node → sanitize_html
2279
// * packages/frontend/misc-page    → sanitize_html
2280
export function sanitize_html_attributes($, node): void {
2281
  $.each(node.attributes, function () {
2282
    // sometimes, "this" is undefined -- #2823
2283
    // @ts-ignore -- no implicit this
2284
    if (this == null) {
2285
      return;
2286
    }
2287
    // @ts-ignore -- no implicit this
2288
    const attrName = this.name;
2289
    // @ts-ignore -- no implicit this
2290
    const attrValue = this.value;
2291
    // remove attribute name start with "on", possible
2292
    // unsafe, e.g.: onload, onerror...
2293
    // remove attribute value start with "javascript:" pseudo
2294
    // protocol, possible unsafe, e.g. href="javascript:alert(1)"
2295
    if (
2296
      attrName?.indexOf("on") === 0 ||
2297
      attrValue?.indexOf("javascript:") === 0
2298
    ) {
2299
      $(node).removeAttr(attrName);
2300
    }
2301
  });
2302
}
2303

2304
// cocalc analytics cookie name
2305
export const analytics_cookie_name = "CC_ANA";
2306

2307
// convert a jupyter kernel language (i.e. "python" or "r", usually short and lowercase)
2308
// to a canonical name.
2309
export function jupyter_language_to_name(lang: string): string {
2310
  if (lang === "python") {
2311
    return "Python";
2312
  } else if (lang === "gap") {
2313
    return "GAP";
2314
  } else if (lang === "sage" || exports.startswith(lang, "sage-")) {
2315
    return "SageMath";
2316
  } else {
2317
    return capitalize(lang);
2318
  }
2319
}
2320

2321
// Find the kernel whose name is closest to the given name.
2322
export function closest_kernel_match(
2323
  name: string,
2324
  kernel_list: immutable.List<immutable.Map<string, any>>,
2325
): immutable.Map<string, any> {
2326
  name = name.toLowerCase().replace("matlab", "octave");
2327
  name = name === "python" ? "python3" : name;
2328
  let bestValue = -1;
2329
  let bestMatch: immutable.Map<string, any> | undefined = undefined;
2330
  for (let i = 0; i < kernel_list.size; i++) {
2331
    const k = kernel_list.get(i);
2332
    if (k == null) {
2333
      // This happened to Harald once when using the "mod sim py" custom image.
2334
      continue;
2335
    }
2336
    // filter out kernels with negative priority (using the priority
2337
    // would be great, though)
2338
    if ((k.getIn(["metadata", "cocalc", "priority"], 0) as number) < 0)
2339
      continue;
2340
    const kernel_name = k.get("name")?.toLowerCase();
2341
    if (!kernel_name) continue;
2342
    let v = 0;
2343
    for (let j = 0; j < name.length; j++) {
2344
      if (name[j] === kernel_name[j]) {
2345
        v++;
2346
      } else {
2347
        break;
2348
      }
2349
    }
2350
    if (
2351
      v > bestValue ||
2352
      (v === bestValue &&
2353
        bestMatch &&
2354
        compareVersionStrings(
2355
          k.get("name") ?? "",
2356
          bestMatch.get("name") ?? "",
2357
        ) === 1)
2358
    ) {
2359
      bestValue = v;
2360
      bestMatch = k;
2361
    }
2362
  }
2363
  if (bestMatch == null) {
2364
    // kernel list could be empty...
2365
    return kernel_list.get(0) ?? immutable.Map<string, string>();
2366
  }
2367
  return bestMatch;
2368
}
2369

2370
// compareVersionStrings takes two strings "a","b"
2371
// and returns 1 is "a" is bigger, 0 if they are the same, and -1 if "a" is smaller.
2372
// By "bigger" we compare the integer and non-integer parts of the strings separately.
2373
// Examples:
2374
//     - "sage.10" is bigger than "sage.9" (because 10 > 9)
2375
//     - "python.1" is bigger than "sage.9" (because "python" > "sage")
2376
//     - "sage.1.23" is bigger than "sage.0.456" (because 1 > 0)
2377
//     - "sage.1.2.3" is bigger than "sage.1.2" (because "." > "")
2378
function compareVersionStrings(a: string, b: string): -1 | 0 | 1 {
2379
  const av: string[] = a.split(/(\d+)/);
2380
  const bv: string[] = b.split(/(\d+)/);
2381
  for (let i = 0; i < Math.max(av.length, bv.length); i++) {
2382
    const l = av[i] ?? "";
2383
    const r = bv[i] ?? "";
2384
    if (/\d/.test(l) && /\d/.test(r)) {
2385
      const vA = parseInt(l);
2386
      const vB = parseInt(r);
2387
      if (vA > vB) {
2388
        return 1;
2389
      }
2390
      if (vA < vB) {
2391
        return -1;
2392
      }
2393
    } else {
2394
      if (l > r) {
2395
        return 1;
2396
      }
2397
      if (l < r) {
2398
        return -1;
2399
      }
2400
    }
2401
  }
2402
  return 0;
2403
}
2404

2405
// Count number of occurrences of m in s-- see http://stackoverflow.com/questions/881085/count-the-number-of-occurences-of-a-character-in-a-string-in-javascript
2406

2407
export function count(str: string, strsearch: string): number {
2408
  let index = -1;
2409
  let count = -1;
2410
  while (true) {
2411
    index = str.indexOf(strsearch, index + 1);
2412
    count++;
2413
    if (index === -1) {
2414
      break;
2415
    }
2416
  }
2417
  return count;
2418
}
2419

2420
// right pad a number using html's &nbsp;
2421
// by default, rounds number to a whole integer
2422
export function rpad_html(num: number, width: number, round_fn?: Function) {
2423
  num = (round_fn ?? Math.round)(num);
2424
  const s = "&nbsp;";
2425
  if (num == 0) return lodash.repeat(s, width - 1) + "0";
2426
  if (num < 0) return num; // TODO not implemented
2427
  const str = `${num}`;
2428
  const pad = Math.max(0, width - str.length);
2429
  return lodash.repeat(s, pad) + str;
2430
}
2431

2432
// Remove key:value's from objects in obj
2433
// recursively, where value is undefined or null.
2434
export function removeNulls(obj) {
2435
  if (typeof obj != "object") {
2436
    return obj;
2437
  }
2438
  if (is_array(obj)) {
2439
    for (const x of obj) {
2440
      removeNulls(x);
2441
    }
2442
    return obj;
2443
  }
2444
  const obj2: any = {};
2445
  for (const field in obj) {
2446
    if (obj[field] != null) {
2447
      obj2[field] = removeNulls(obj[field]);
2448
    }
2449
  }
2450
  return obj2;
2451
}
2452

2453
const academicCountry = new RegExp(/\.(ac|edu)\...$/);
2454

2455
// test if a domain belongs to an academic instition
2456
// TODO: an exhaustive test must probably use the list at https://github.com/Hipo/university-domains-list
2457
export function isAcademic(s?: string): boolean {
2458
  if (!s) return false;
2459
  const domain = s.split("@")[1];
2460
  if (!domain) return false;
2461
  if (domain.endsWith(".edu")) return true;
2462
  if (academicCountry.test(domain)) return true;
2463
  return false;
2464
}
2465

2466
/**
2467
 * Test, if the given object is a valid list of JSON-Patch operations.
2468
 * @returns boolean
2469
 */
2470
export function test_valid_jsonpatch(patch: any): boolean {
2471
  if (!is_array(patch)) {
2472
    return false;
2473
  }
2474
  for (const op of patch) {
2475
    if (!is_object(op)) {
2476
      return false;
2477
    }
2478
    if (op["op"] == null) {
2479
      return false;
2480
    }
2481
    if (
2482
      !["add", "remove", "replace", "move", "copy", "test"].includes(op["op"])
2483
    ) {
2484
      return false;
2485
    }
2486
    if (op["path"] == null) {
2487
      return false;
2488
    }
2489
    if (op["from"] != null && typeof op["from"] !== "string") {
2490
      return false;
2491
    }
2492
    // we don't test on value
2493
  }
2494
  return true;
2495
}
2496

2497
export function rowBackground({
2498
  index,
2499
  checked,
2500
}: {
2501
  index: number;
2502
  checked?: boolean;
2503
}): string {
2504
  if (checked) {
2505
    if (index % 2 === 0) {
2506
      return "#a3d4ff";
2507
    } else {
2508
      return "#a3d4f0";
2509
    }
2510
  } else if (index % 2 === 0) {
2511
    return "#f4f4f4";
2512
  } else {
2513
    return "white";
2514
  }
2515
}
2516

2517
export function firstLetterUppercase(str: string | undefined) {
2518
  if (str == null) return "";
2519
  return str.charAt(0).toUpperCase() + str.slice(1);
2520
}
2521

2522
const randomColorCache = new LRU<string, string>({ max: 100 });
2523

2524
/**
2525
 * For a given string s, return a random bright color, but not too bright.
2526
 * Use a hash to make this random, but deterministic.
2527
 *
2528
 * opts:
2529
 * - min: minimum value for each channel
2530
 * - max: maxium value for each channel
2531
 * - diff: mimimum difference across channels (increase, to avoid dull gray colors)
2532
 * - seed: seed for the random number generator
2533
 */
2534
export function getRandomColor(
2535
  s: string,
2536
  opts?: { min?: number; max?: number; diff?: number; seed?: number },
2537
): string {
2538
  const diff = opts?.diff ?? 0;
2539
  const min = clip(opts?.min ?? 120, 0, 254);
2540
  const max = Math.max(min, clip(opts?.max ?? 230, 1, 255));
2541
  const seed = opts?.seed ?? 0;
2542

2543
  const key = `${s}-${min}-${max}-${diff}-${seed}`;
2544
  const cached = randomColorCache.get(key);
2545
  if (cached) {
2546
    return cached;
2547
  }
2548

2549
  let iter = 0;
2550
  const iterLimit = "z".charCodeAt(0) - "A".charCodeAt(0);
2551
  const mod = max - min;
2552

2553
  while (true) {
2554
    // seed + s + String.fromCharCode("A".charCodeAt(0) + iter)
2555
    const val = `${seed}-${s}-${String.fromCharCode("A".charCodeAt(0) + iter)}`;
2556
    const hash = sha1(val)
2557
      .split("")
2558
      .reduce((a, b) => ((a << 6) - a + b.charCodeAt(0)) | 0, 0);
2559
    const r = (((hash >> 0) & 0xff) % mod) + min;
2560
    const g = (((hash >> 8) & 0xff) % mod) + min;
2561
    const b = (((hash >> 16) & 0xff) % mod) + min;
2562

2563
    iter += 1;
2564
    if (iter <= iterLimit && diff) {
2565
      const diffVal = Math.abs(r - g) + Math.abs(g - b) + Math.abs(b - r);
2566
      if (diffVal < diff) continue;
2567
    }
2568
    const col = `rgb(${r}, ${g}, ${b})`;
2569
    randomColorCache.set(key, col);
2570
    return col;
2571
  }
2572
}
2573

2574
export function hexColorToRGBA(col: string, opacity?: number): string {
2575
  const r = parseInt(col.slice(1, 3), 16);
2576
  const g = parseInt(col.slice(3, 5), 16);
2577
  const b = parseInt(col.slice(5, 7), 16);
2578

2579
  if (opacity && opacity <= 1 && opacity >= 0) {
2580
    return `rgba(${r},${g},${b},${opacity})`;
2581
  } else {
2582
    return `rgb(${r},${g},${b})`;
2583
  }
2584
}
2585

2586
// returns an always positive integer, not negative ones. useful for "scrolling backwards", etc.
2587
export function strictMod(a: number, b: number): number {
2588
  return ((a % b) + b) % b;
2589
}
2590

2591
export function clip(val: number, min: number, max: number): number {
2592
  return Math.min(Math.max(val, min), max);
2593
}
2594

2595
/**
2596
 * Converts an integer to an English word, but only for small numbers and reverts to a digit for larger numbers
2597
 */
2598
export function smallIntegerToEnglishWord(val: number): string | number {
2599
  if (!Number.isInteger(val)) return val;
2600
  switch (val) {
2601
    case 0:
2602
      return "zero";
2603
    case 1:
2604
      return "one";
2605
    case 2:
2606
      return "two";
2607
    case 3:
2608
      return "three";
2609
    case 4:
2610
      return "four";
2611
    case 5:
2612
      return "five";
2613
    case 6:
2614
      return "six";
2615
    case 7:
2616
      return "seven";
2617
    case 8:
2618
      return "eight";
2619
    case 9:
2620
      return "nine";
2621
    case 10:
2622
      return "ten";
2623
    case 11:
2624
      return "eleven";
2625
    case 12:
2626
      return "twelve";
2627
    case 13:
2628
      return "thirteen";
2629
    case 14:
2630
      return "fourteen";
2631
    case 15:
2632
      return "fifteen";
2633
    case 16:
2634
      return "sixteen";
2635
    case 17:
2636
      return "seventeen";
2637
    case 18:
2638
      return "eighteen";
2639
    case 19:
2640
      return "nineteen";
2641
    case 20:
2642
      return "twenty";
2643
  }
2644
  return val;
2645
}
2646

2647
export function numToOrdinal(val: number): string {
2648
  // 1 → 1st, 2 → 2nd, 3 → 3rd, 4 → 4th, ... 21 → 21st, ... 101 → 101st, ...
2649
  if (!Number.isInteger(val)) return `${val}th`;
2650
  const mod100 = val % 100;
2651
  if (mod100 >= 11 && mod100 <= 13) {
2652
    return `${val}th`;
2653
  }
2654
  const mod10 = val % 10;
2655
  switch (mod10) {
2656
    case 1:
2657
      return `${val}st`;
2658
    case 2:
2659
      return `${val}nd`;
2660
    case 3:
2661
      return `${val}rd`;
2662
    default:
2663
      return `${val}th`;
2664
  }
2665
}
2666

2667
export function hoursToTimeIntervalHuman(num: number): string {
2668
  if (num < 24) {
2669
    const n = round1(num);
2670
    return `${n} ${plural(n, "hour")}`;
2671
  } else if (num < 24 * 7) {
2672
    const n = round1(num / 24);
2673
    return `${n} ${plural(n, "day")}`;
2674
  } else {
2675
    const n = round1(num / (24 * 7));
2676
    return `${n} ${plural(n, "week")}`;
2677
  }
2678
}
2679

2680
/**
2681
 * Return the last @lines lines of string s, in an efficient way. (e.g. long stdout, and return last 3 lines)
2682
 */
2683
export function tail(s: string, lines: number) {
2684
  if (lines < 1) return "";
2685

2686
  let lineCount = 0;
2687
  let lastIndex = s.length - 1;
2688

2689
  // Iterate backwards through the string, searching for newline characters
2690
  while (lastIndex >= 0 && lineCount < lines) {
2691
    lastIndex = s.lastIndexOf("\n", lastIndex);
2692
    if (lastIndex === -1) {
2693
      // No more newlines found, return the entire string
2694
      return s;
2695
    }
2696
    lineCount++;
2697
    lastIndex--;
2698
  }
2699

2700
  // Return the substring starting from the next character after the last newline
2701
  return s.slice(lastIndex + 2);
2702
}
2703

2704
export function basePathCookieName({
2705
  basePath,
2706
  name,
2707
}: {
2708
  basePath: string;
2709
  name: string;
2710
}): string {
2711
  return `${basePath.length <= 1 ? "" : encodeURIComponent(basePath)}${name}`;
2712
}
2713

2714
export function isNumericString(str: string): boolean {
2715
  // https://stackoverflow.com/questions/175739/how-can-i-check-if-a-string-is-a-valid-number
2716
  if (typeof str != "string") {
2717
    return false; // we only process strings!
2718
  }
2719
  return (
2720
    // @ts-ignore
2721
    !isNaN(str) && // use type coercion to parse the _entirety_ of the string (`parseFloat` alone does not do this)...
2722
    !isNaN(parseFloat(str))
2723
  ); // ...and ensure strings of whitespace fail
2724
}
2725

2726
// This is needed in browsers, where toString('base64') doesn't work
2727
// and .toBase64(). This also works on buffers.  In nodejs there is
2728
// toString('base64'), but that seems broken in some cases and a bit
2729
// dangerous since toString('base64') in the browser is just toString(),
2730
// which is very different.
2731
export function uint8ArrayToBase64(uint8Array: Uint8Array) {
2732
  let binaryString = "";
2733
  for (let i = 0; i < uint8Array.length; i++) {
2734
    binaryString += String.fromCharCode(uint8Array[i]);
2735
  }
2736
  return btoa(binaryString);
2737
}
2738

2739