gen.d 50.4 KB
Newer Older
Vladimir Panteleev's avatar
Vladimir Panteleev committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 * This is free and unencumbered software released into the public domain.
 *
 * Anyone is free to copy, modify, publish, use, compile, sell, or
 * distribute this software, either in source code form or as a compiled
 * binary, for any purpose, commercial or non-commercial, and by any
 * means.
 *
 * In jurisdictions that recognize copyright laws, the author or authors
 * of this software dedicate any and all copyright interest in the
 * software to the public domain. We make this dedication for the benefit
 * of the public at large and to the detriment of our heirs and
 * successors. We intend this dedication to be an overt act of
 * relinquishment in perpetuity of all present and future rights to this
 * software under copyright law.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 *
 * For more information, please refer to <http://unlicense.org>
 */

28
29
import core.math;

30
import ae.utils.array;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
31
import ae.utils.json;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
32
import ae.utils.xmllite;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
33

Vladimir Panteleev's avatar
Vladimir Panteleev committed
34
import std.algorithm.comparison;
35
import std.algorithm.iteration;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
36
import std.algorithm.mutation;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
37
import std.algorithm.searching;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
38
39
40
import std.algorithm.sorting;
import std.array;
import std.conv;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
41
import std.file;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
42
import std.format;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
43
import std.json;
44
import std.range;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
45
import std.stdio;
46
import std.string;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
47
48
49
50
51
52
53
54
55

struct SegmentMap
{
	string type, viewableId;

	struct Segment
	{
		struct UI
		{
Vladimir Panteleev's avatar
Vladimir Panteleev committed
56
			int[2][] interactionZones;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
57
58
59
60
61
62
63
64
65
66
67
68
69
70
		}
		UI ui;
		int startTimeMs;
		int endTimeMs;
		struct Next { int weight; }
		Next[string] next;
		string defaultNext;
		bool storyEnd, credits;
	}
	Segment[string] segments;
	string initialSegment;
	struct UI { bool resetBookmarkInCredits; }
	UI ui;
}
Vladimir Panteleev's avatar
Vladimir Panteleev committed
71
SegmentMap segmentMap;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
static this() { segmentMap = readText("../en/assets/SegmentMap.js").findSplit("=")[2].jsonParse!SegmentMap; }

struct ImpressionData
{
	string type;
	struct Data
	{
		JSONFragment[string] persistent;
	} Data data;
}

struct Bandersnatch
{
	struct Video
	{
		struct Atom(T)
		{
			@JSONName("$type") string type;
			@JSONName("$size") long size;
			T value;
		}
		struct InteractiveVideoMoments
		{
			string type;
			struct ChoicePointNavigatorMetadata
			{
				struct Config
				{
					string lockStrategy;
					string selectionType;
					bool playerControlsTenSecondsControls;
					int maxSnapshotsToDisplay;
					string timelineContainerOverrideClass;
					bool timelineShowColumnLabel;
					struct Breakpoint
					{
						int cols;
						int minWidth;
					} Breakpoint[] timelineLayoutBreakpoints;
				} Config config;
				struct Storylines
				{
					struct Storyline
					{
						string id;
						struct Chapter
						{
							string id;
							string[] source;
							string[] target;
						} Chapter[] chapters;
					} Storyline[] list;
				} Storylines storylines;
				string type;
				struct ChoicePointsMetadata
				{
					string[] timelineLabel;
					struct ChoicePoint
					{
						string[] choices;
						long startTimeMs;
						string description;
						struct Image
						{
							string[string] styles;
						} Image image;
					} ChoicePoint[string] choicePoints;
					string choices;
				} ChoicePointsMetadata choicePointsMetadata;
			} ChoicePointNavigatorMetadata choicePointNavigatorMetadata;
			struct CommonMetadata
			{
				// struct Layout
				// {
				// 	struct Timer
				// 	{
				// 		int minPercentage;
				// 		bool simpleBarTimer;
				// 		bool preventInAndOutAnimation;
				// 		bool timerAlwaysVisible;
				// 		string type;
				// 		string layoutType;
				// 	} Timer timer;
				// } Layout[string] layouts;
				JSONFragment layouts;
				struct Settings
				{
					bool randomInitialDefault;
					bool disableToggleDefault;
				} Settings settings;
			} CommonMetadata commonMetadata;
			string[] segmentHistory;
			JSONFragment[string] stateHistory;
			string[] snapshots;
			struct Moment
			{
				string type;
				long startMs, endMs;
				JSONFragment precondition;
				ImpressionData impressionData;
				long[2] activationWindow;
				string id;
				string segmentId;
				string layoutType;
				long uiDisplayMS, uiHideMS;
				int defaultChoiceIndex;
				long choiceActivationThresholdMS;
				struct Choice
				{
					string id;
					string sg;
					string segmentId;
					string optionType; // !!!
					long startTimeMs;
					ImpressionData impressionData;
					JSONFragment trackingInfo;
					string text;
					struct Image
					{
						string[string] styles;
					} Image image;
					string code;
				}
				Choice[] choices;
				string[string] trackingInfo;
				long uiInteractionStartMS;
				struct Config
				{
					bool intervalBasedVideoTimer;
					bool disableImmediateSceneTransition;
					bool disablePrematureUserInteraction;
					bool hideChoiceLabelWhenChoiceHasImage;
					bool randomInitialDefault;
					string defaultSelectType;
					bool hasMultipleChoiceInput;
				} Config config;
				JSONFragment inputConfig;
				string[string] action;
			}
			Moment[][string] momentsBySegment;
			JSONFragment[string] preconditions;
			string audioLocale;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
214
			JSONFragment[][string] segmentGroups;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
215
216
217
218
219
220
221
		}
		Atom!InteractiveVideoMoments interactiveVideoMoments;
	}
	Video[string] videos;
}
Bandersnatch bandersnatch;
static this() { bandersnatch = readText("../en/assets/bandersnatch.js").findSplit("=")[2].jsonParse!Bandersnatch; }
Vladimir Panteleev's avatar
Vladimir Panteleev committed
222

Vladimir Panteleev's avatar
Vladimir Panteleev committed
223
224
225
Bandersnatch.Video.InteractiveVideoMoments* video;
static this() { video = &bandersnatch.videos["80988062"].interactiveVideoMoments.value; }

226
227
enum optimize = true;

228
229
enum bestVariableReadOrderFN = "varorder-read.txt";
enum bestVariableWriteOrderFN = "varorder-write.txt";
Vladimir Panteleev's avatar
Vladimir Panteleev committed
230
bool[string][string] allVariableValues;
231
232
string[] varReadOrder, varWriteOrder;
bool draft;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
static this()
{
	void scanImpressionData(ref ImpressionData impressionData)
	{
		foreach (name, value; impressionData.data.persistent)
			allVariableValues[name][value.json.strip] = true;
	}

	foreach (id, moments; video.momentsBySegment)
		foreach (moment; moments)
		{
			scanImpressionData(moment.impressionData);
			foreach (choice; moment.choices)
				scanImpressionData(choice.impressionData);
		}

249
250
	varReadOrder  = optimize && bestVariableReadOrderFN .exists ? bestVariableReadOrderFN .readText.splitLines : allVariableValues.keys.sort.release;
	varWriteOrder = optimize && bestVariableWriteOrderFN.exists ? bestVariableWriteOrderFN.readText.splitLines : allVariableValues.keys.sort.release;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
251
252
}

253
254
255
struct TextData
{
	string[string] segmentDescriptions;
256
257
258
259
260
261
	struct Var
	{
		string readText;
		string[string] readValueText, writeValueText;
	}
	Var[string] vars;
262
	string[][string] momentDescriptions;
263
264
265
266
}
TextData textData;
static this()
{
267
268
269
270
	enum dataFn = "data.org";
	enum sanitizedDataFn = "data.json";

	if (dataFn.exists && (!sanitizedDataFn.exists || sanitizedDataFn.timeLastModified < dataFn.timeLastModified))
271
	{
272
273
		TextData textData;
		auto lines = dataFn.readText().splitLines();
Vladimir Panteleev's avatar
Vladimir Panteleev committed
274
		string[] segmentLines, varLines, momentLines, macroLines;
275
276
277
278
279
		string section;
		foreach (line; lines)
			if (line.startsWith("*"))
				section = line;
			else
280
281
			if (line.startsWith("| "))
			{
Vladimir Panteleev's avatar
Vladimir Panteleev committed
282
283
284
				if (section == "* Macros")
					macroLines ~= line;
				else
285
286
287
288
289
				if (section == "* Segments")
					segmentLines ~= line;
				else
				if (section == "* Variables")
					varLines ~= line;
290
291
292
				else
				if (section == "* Moments")
					momentLines ~= line;
293
294
			}

295
		string[2][] macros;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
296
297
298
299
		foreach (line; macroLines[1..$])
		{
			auto parts = line.split("|");
			if (parts[1].length)
300
				macros ~= [parts[1].strip, parts[2].strip];
Vladimir Panteleev's avatar
Vladimir Panteleev committed
301
		}
302
		macros.sort!((a, b) => a[0].length > b[0].length);
Vladimir Panteleev's avatar
Vladimir Panteleev committed
303
304
305

		string replaceMacros(string s)
		{
306
307
			foreach (pair; macros)
				s = s.replace(pair[0], pair[1]);
Vladimir Panteleev's avatar
Vladimir Panteleev committed
308
309
310
			return s;
		}

311
312
313
		foreach (line; segmentLines[1..$])
		{
			auto parts = line.split("|");
314
315
			auto desc = parts[5].strip;
			if (desc.length)
Vladimir Panteleev's avatar
Vladimir Panteleev committed
316
				textData.segmentDescriptions[parts[1].strip] = replaceMacros(desc);
317
		}
318
319
320
321
322

		foreach (line; varLines[1..$])
		{
			auto parts = line.split("|").map!strip.array;
			TextData.Var var;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
323
			var.readText = parts[3].length ? replaceMacros(parts[3]) : null;
324
			foreach (col; parts[4 .. $])
325
326
327
328
				if (col.length)
				{
					auto colParts = col.split("#").map!strip.array;
					if (colParts.length > 1)
Vladimir Panteleev's avatar
Vladimir Panteleev committed
329
						var.writeValueText[colParts[0]] = replaceMacros(colParts[1]);
330
					if (colParts.length > 2)
Vladimir Panteleev's avatar
Vladimir Panteleev committed
331
						var.readValueText[colParts[0]] = replaceMacros(colParts[2]);
332
333
334
				}
			textData.vars[parts[1]] = var;
		}
335
336
337
338
339
340

		foreach (line; momentLines[1..$])
		{
			auto parts = line.split("|");
			auto desc = parts[6].strip;
			if (desc.length)
Vladimir Panteleev's avatar
Vladimir Panteleev committed
341
				textData.momentDescriptions.require(parts[1].strip).putExpand(parts[2].strip.to!size_t, replaceMacros(desc));
342
		}
343
344

		textData.toPrettyJson.toFile(sanitizedDataFn);
345
	}
346
347

	textData = sanitizedDataFn.readText.jsonParse!TextData;
348
}
Vladimir Panteleev's avatar
Vladimir Panteleev committed
349

350
void main(string[] args)
Vladimir Panteleev's avatar
Vladimir Panteleev committed
351
{
352
353
354
355
356
357
	writeln(segmentMap.segments.length, " segments");
	writeln(allVariableValues.length, " variables");
	writeln(video.momentsBySegment.byValue.joiner.filter!(m => m.choices).walkLength, " choices");
	writeln(video.segmentGroups.length, " segment groups");
	writeln(video.preconditions.length, " preconditions");

358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
	if (args.length == 1)
	{
		//checkContiguity();
		//genSegmentGraph();
		genGraph();
		genDataTemplates();
		genHTML();
	}
	else
		switch (args[1])
		{
			case "opt":
				return optimizeVars();
			default:
				assert(0);
		}
Vladimir Panteleev's avatar
Vladimir Panteleev committed
374
}
Vladimir Panteleev's avatar
Vladimir Panteleev committed
375

376
void genSegmentGraph()
Vladimir Panteleev's avatar
Vladimir Panteleev committed
377
{
378
	auto f = File("segments.dot", "w");
Vladimir Panteleev's avatar
Vladimir Panteleev committed
379
380
	f.writeln("digraph {");
	foreach (name, segment; segmentMap.segments)
Vladimir Panteleev's avatar
Vladimir Panteleev committed
381
	{
Vladimir Panteleev's avatar
Vladimir Panteleev committed
382
383
		foreach (nextName, next; segment.next)
			f.writefln("\t%(%s%) -> %(%s%);", [name], [nextName]);
Vladimir Panteleev's avatar
Vladimir Panteleev committed
384
	}
Vladimir Panteleev's avatar
Vladimir Panteleev committed
385
386
	f.writeln("}");
}
Vladimir Panteleev's avatar
Vladimir Panteleev committed
387

388
struct Graph
389
{
390
391
392
393
394
395
396
	alias NodeIndexVal = size_t;
	struct NodeIndex
	{
		NodeIndexVal val = NodeIndexVal.max;
		bool opCast(T)() if (is(T==bool)) { return val != NodeIndexVal.max; }
	}
	struct Edge
397
	{
398
		enum Kind { undefined, normal, segment, choiceDefault, segmentGroupDefault, nextDefault, yes, no, unreachable }
399
400
401
402
		Kind kind;
		NodeIndex target;
		string label;
		bool reversed;
403
		bool noCap;
404
405

		void put(NodeIndex source, ref File f)
406
		{
407
408
409
410
411
412
			if (reversed)
				f.writef("\tn%d -> n%d [dir=back]", target.val, source.val);
			else
				f.writef("\tn%d -> n%d"           , source.val, target.val);
			if (label)
				f.writef(" [label=%(%s%)]", [label]);
413
414
			if (noCap)
				f.write(" [arrowhead=none]");
415
416
			final switch (kind)
			{
417
				case Kind.undefined          : assert(false);
418
419
				case Kind.normal             : break;
				case Kind.segment            : f.write(" [penwidth=2] [color=\"#bbeeee\"]"); break;
420
421
422
				case Kind.choiceDefault      : f.write(" [penwidth=2]"); break;
				case Kind.segmentGroupDefault: f.write(" [penwidth=2] [style=dashed]"); break;
				case Kind.nextDefault        : f.write(" [penwidth=2] [style=dotted]"); break;
423
424
				case Kind.yes                : f.write(" [penwidth=2] [color=\"#00bb00\"]"); break;
				case Kind.no                 : f.write(" [penwidth=2] [color=\"#ff0000\"] [style=dashed]"); break;
425
				case Kind.unreachable        : f.write(" [style=dotted]"); break;
426
427
			}
			f.writeln(";");
428
429
		}
	}
430
	struct Node
431
	{
Vladimir Panteleev's avatar
Vladimir Panteleev committed
432
		enum Kind { segment, ending, recap, precondition, preconditionResult, impression, choices, choice, segmentGroup, dummy, point, error }
433
434
		Kind kind;
		string label;
435
436
		bool html;
		string tooltip;
437
		Edge[] edges;
438
		bool deleted, gc;
439
440

		void put(NodeIndex index, ref File f)
441
		{
442
443
			f.writef("\tn%d", index.val);
			if (label)
444
445
			{
				if (html)
446
					f.writef(" [label=<%s>]", label.replace(`</b> <b>`, ` `));
447
448
449
450
451
				else
					f.writef(" [label=%(%s%)]", [label]);
			}
			if (tooltip)
				f.writef(" [tooltip=%(%s%)]", [tooltip]);
452
453
			final switch (kind)
			{
454
				case Kind.segment           : f.write(" [shape=box    , fillcolor=\"#bbeeee\", color=\"#446666\",                  style=filled, penwidth=2]"); break;
455
				case Kind.ending            : f.write(" [shape=box    , fillcolor=\"#bbeebb\", color=\"#446644\",                  style=filled, penwidth=2]"); break;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
456
				case Kind.recap             : f.write(" [shape=box    , fillcolor=\"#dddddd\", color=\"#555555\",                  style=filled, penwidth=2]"); break;
457
458
				case Kind.precondition      : f.write(" [shape=diamond, fillcolor=\"#ffffee\", color=\"#ffffaa\", fontcolor=black, style=filled, penwidth=2]"); break;
				case Kind.preconditionResult: f.write(" [shape=oval   , fillcolor=\"#ffffee\", color=\"#ffffaa\", fontcolor=black, style=filled, penwidth=2]"); break;
459
				case Kind.impression        : f.write(" [shape=box    , fillcolor=\"#ffeeff\", color=\"#ffaaff\", fontcolor=black, style=filled, penwidth=2]"); break;
460
461
				case Kind.choices           : f.write(" [shape=diamond, fillcolor=\"#bbeeee\", color=\"#446666\", fontcolor=black, style=filled, penwidth=2]"); break;
				case Kind.choice            : f.write(" [shape=box    , fillcolor=\"#000000\", color=\"#ffffff\", fontcolor=white, style=filled, penwidth=2]"); break;
462
				case Kind.segmentGroup      : assert(false);
463
				case Kind.dummy             : assert(false);
464
				case Kind.point             : f.write(" [shape=point  , width=0,               color=\"#ffffff\",                  style=invis             ]"); break;
465
				case Kind.error             : f.write(" [shape=box    , fillcolor=\"#eebbbb\", color=\"#664444\",                  style=filled, penwidth=2]"); break;
466
467
468
469
			}
			f.writeln(";");
			foreach (edge; edges)
				edge.put(index, f);
470
471
		}
	}
472
473
	Node[] nodes;

474
	NodeIndex addNode(Node.Kind kind, string label, bool html = false, string tooltip = null)
475
	{
476
		nodes ~= Node(kind, label, html, tooltip);
477
478
479
480
481
482
483
		return NodeIndex(nodes.length - 1);
	}
	void addEdge(Edge.Kind kind, NodeIndex from, NodeIndex to, string label = null, bool reversed = false)
	{
		nodes[from.val].edges ~= Edge(kind, to, label, reversed);
	}

484
	NodeIndex firstNode;
485
	private NodeIndex[] unreachableNodes;
486

487
488
	void put(File f)
	{
489
490
491
492
493
494
495
496
497
498
499
500
		f.writeln(`digraph {`);
		f.writeln(`	graph [bgcolor=black];`);
		f.writeln(`	node [style=filled];`);
		f.writeln(`	edge [color=white fontcolor=white fontname="helvetica"];`);
		f.writeln(`	node [fontname="helvetica"];`);
		f.writeln(``);

		{
			auto startNode = addNode(Node.Kind.choice, "START");
			addEdge(Edge.Kind.normal, startNode, firstNode);
			nodes[startNode.val].put(startNode, f);
			nodes[startNode.val].deleted = true;
501
502
503
504

			auto unreachableNode = addNode(Node.Kind.error, "UNREACHABLE");
			foreach (n; unreachableNodes)
				if (n != firstNode)
505
					addEdge(Edge.Kind.unreachable, unreachableNode, n);
506
507
			nodes[unreachableNode.val].put(unreachableNode, f);
			nodes[unreachableNode.val].deleted = true;
508
509

			f.writefln(`	{ rank=same; n%d; n%d; }`, startNode.val, unreachableNode.val);
510
511
		}
		f.writeln(`subgraph cluster_main {`);
512
513

		foreach (i, node; nodes)
514
515
			if (!node.deleted)
				node.put(NodeIndex(i), f);
516

517
518
		f.writeln(`}`);
		f.writeln(`}`);
519
	}
520

521
	void finalize()
522
	{
523
524
		bool changes = true;

525
		void replace(NodeIndexVal from, NodeIndexVal to, bool doDelete = true)
526
		{
527
528
			if (doDelete)
				nodes[from].deleted = true;
529
			foreach (ref node; nodes)
530
531
532
533
534
				if (!node.deleted)
					foreach (ref edge; node.edges)
						if (edge.target.val == from)
							edge.target.val = to;
			changes = true;
535
536
		}

537
538
539
540
541
542
543
544
545
546
547
548
		static Edge.Kind mergeEdgeKind(Edge.Kind a, Edge.Kind b)
		{
			if (a == b)
				return a;
			if (a > b)
				swap(a, b);
			if (a.among(Edge.Kind.normal, Edge.Kind.choiceDefault, Edge.Kind.segmentGroupDefault) &&
				b.among(Edge.Kind.normal, Edge.Kind.choiceDefault, Edge.Kind.segmentGroupDefault))
				return a;
			return Edge.Kind.undefined;
		}

549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
		string mergeTooltips(R)(R nodes)
		{
			static immutable tooltipDelim = "\n-------\n";
			return nodes
				.map!(node => node
					.tooltip
					.strip
					.split(tooltipDelim)
				)
				.joiner
				.filter!(s => s.length)
				.array
				.sort
				.uniq
				.join(tooltipDelim);
		}

566
567
568
569
570
571
572
573
		foreach (nodeIndex, ref node; nodes)
			if (node.kind == Node.Kind.dummy)
			{
				assert(node.edges.length == 1, "Dummy node with not one edge: " ~ node.label);
				assert(node.edges[0].kind == Edge.Kind.normal);
				replace(nodeIndex, node.edges[0].target.val);
			}

574
	changesLoop:
575
		static if (optimize)
576
		while (changes)
577
		{
578
579
			changes = false;

580
581
582
583
584
585
586
587
588
589
590
			// Try to shift choices behind identical segment start nodes.
			// Before: o<8=8
			// After : o-o<8
		choiceShiftLoop:
			foreach (nodeIndex, ref node; nodes)
				if (node.kind == Node.Kind.precondition && node.edges.length >= 2)
				{
					auto firstTarget = &nodes[node.edges[0].target.val];
					foreach (ref edge; node.edges)
					{
						auto target = &nodes[edge.target.val];
Vladimir Panteleev's avatar
Vladimir Panteleev committed
591
						if (!target.kind.among(Node.Kind.segment, Node.Kind.ending, Node.Kind.recap, Node.Kind.impression, Node.Kind.choices, Node.Kind.choice) ||
592
							target.kind != firstTarget.kind ||
593
594
							target.label != firstTarget.label ||
							target.edges.length != 1 ||
595
596
597
598
							mergeEdgeKind(target.edges[0].kind, firstTarget.edges[0].kind) == Edge.Kind.undefined ||
							target.edges[0].label    != firstTarget.edges[0].label ||
							target.edges[0].reversed != firstTarget.edges[0].reversed ||
							target.edges[0].noCap    != firstTarget.edges[0].noCap ||
599
							(target.kind == Node.Kind.choices && nodes[target.edges[0].target.val].edges.length != 1) ||
600
601
602
603
							false)
							continue choiceShiftLoop;
					}

604
					auto newSegmentNode = addNode(firstTarget.kind,
605
						firstTarget.label, firstTarget.html,
606
						mergeTooltips(node.edges.map!(edge => nodes[edge.target.val])),
607
608
					);

609
610
					auto edgeKind = node.edges.map!(edge => nodes[edge.target.val].edges[0].kind).reduce!mergeEdgeKind;

611
612
613
614
					foreach (ref edge; node.edges)
					{
						auto target = &nodes[edge.target.val];
						target.gc = true;
615
						edge.target = target.edges[0].target;
616
					}
617
618

					auto edge = firstTarget.edges[0];
619
					edge.kind = edgeKind;
620
621
622
623
624
625
					edge.target = NodeIndex(nodeIndex);

					replace(nodeIndex, newSegmentNode.val, false);

					nodes[newSegmentNode.val].edges ~= edge;
					continue changesLoop; // nodes was expanded, we are iterating over an old slice
626
627
				}

628
			NodeIndexVal[Node] dups;
629
			static Node hashable(Node node) { node.tooltip = null; return node; }
630
631
632
			foreach (nodeIndex, ref node; nodes)
				if (!node.deleted)
				{
633
					auto oldIndex = dups.require(hashable(node), nodeIndex);
634
					if (oldIndex != nodeIndex)
635
636
					{
						nodes[oldIndex].tooltip = mergeTooltips([nodes[oldIndex], node]);
637
						replace(nodeIndex, oldIndex);
638
					}
639
640
				}
		}
641

642
643
644
645
646
		foreach (ref node; nodes)
			foreach (ref edge; node.edges)
				if (nodes[edge.target.val].kind == Node.Kind.point)
					edge.noCap = true;

647
		auto nodeReachable = new bool[nodes.length];
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
		changes = true;
		while (changes)
		{
			changes = false;
			nodeReachable[] = false;

			foreach (ref node; nodes)
				if (!node.deleted)
					foreach (ref edge; node.edges)
						nodeReachable[edge.target.val] = true;

			foreach (nodeIndex, reachable; nodeReachable)
				if (!reachable && !nodes[nodeIndex].deleted && nodes[nodeIndex].gc)
				{
					nodes[nodeIndex].deleted = true;
					changes = true;
				}
		}

667
668
		foreach (nodeIndex, reachable; nodeReachable)
			if (!reachable && !nodes[nodeIndex].deleted)
669
				unreachableNodes ~= NodeIndex(nodeIndex);
670
671
672
673
674
675

		foreach (ref node; nodes)
			if (!node.deleted)
				foreach (ref edge; node.edges)
					if (nodes[edge.target.val].label == "Rewind!") // TODO: localization
						edge.reversed = true;
676
	}
677
678
}

679
680
string wrapNodeText(string html)
{
Vladimir Panteleev's avatar
Vladimir Panteleev committed
681
	assert(html.length, "Empty node!");
682
683
	if (draft)
		return html;
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742

	static struct Word
	{
		string html;
		size_t width;
	}
	Word[] words;

	{
		Word word;
		bool inTag;

		foreach (i, dchar c; html)
		{
			if (inTag)
			{
				if (c == '>')
					inTag = false;
			}
			else
			if (c == '<')
				inTag = true;
			else
			if (c == ' ')
			{
				words ~= word;
				word = Word.init;
				continue;
			}
			else
				word.width++;
			word.html ~= c;
		}
		words ~= word;
	}

	string[] tryWrap(size_t width)
	{
		string[] lines;
		size_t currentWidth;
		foreach (ref word; words)
		{
			if (!lines || (currentWidth > 0 && currentWidth + word.width > width))
			{
				lines ~= null;
				currentWidth = 0;
			}
			if (lines[$-1].length)
				lines[$-1] ~= ' ';
			lines[$-1] ~= word.html;
			currentWidth += word.width;
		}
		return lines;
	}

	auto textWidth = words.map!(word => word.width).sum + words.length - 1;
	auto initWidth = cast(int)(sqrt(float(textWidth)) * 2).clamp(15, 30);

	auto width = initWidth;
743
	while (width && tryWrap(width - 1).length == tryWrap(width).length)
744
745
		width--;

746
	return tryWrap(width).join("<br/>").strip;
747
748
}

Vladimir Panteleev's avatar
Vladimir Panteleev committed
749
Graph getGraph()
750
751
752
753
754
{
	Graph g;
	alias Node = Graph.NodeIndex;
	alias NodeKind = Graph.Node.Kind;
	alias EdgeKind = Graph.Edge.Kind;
755

756
	auto choicePoints = video.choicePointNavigatorMetadata.choicePointsMetadata.choicePoints;
757

Vladimir Panteleev's avatar
Vladimir Panteleev committed
758
759
760
761
762
	static NodeKind segmentNodeKind(string label)
	{
		// TODO: unlocalizable
		if (label == "Rewind!" || label.startsWith("Fast-forward") || label.startsWith("(Abridged)"))
			return NodeKind.recap;
763
		if (label.startsWith("<b>Game Over.</b>") || label.startsWith("<b>The End.</b>") || label.startsWith("<b>Left:</b>") || label.startsWith("<b>Right:</b>") || label.startsWith("<b>TV:</b>"))
Vladimir Panteleev's avatar
Vladimir Panteleev committed
764
765
766
			return NodeKind.ending;
		return NodeKind.segment;
	}
Vladimir Panteleev's avatar
Vladimir Panteleev committed
767

768
769
770
	// Pre-create segment and segment group nodes
	Node[string] segmentNodes, segmentGroupNodes;
	foreach (id, segment; segmentMap.segments)
771
	{
Vladimir Panteleev's avatar
Vladimir Panteleev committed
772
		auto description = textData.segmentDescriptions.get(id, null).findSplit("#")[0].strip;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
773
		auto kind = segmentNodeKind(description);
774
775
776
		foreach (moment; video.momentsBySegment.get(id, null))
			if (moment.type != "notification:playbackImpression" && !moment.config.disableImmediateSceneTransition)
				kind = NodeKind.ending;
777
778
		auto tooltip = format("Segment ID: %s\nStart: %s\nEnd: %s", id, formatTimestamp(segment.startTimeMs), formatTimestamp(segment.endTimeMs));
		Node node;
Vladimir Panteleev's avatar
Vladimir Panteleev committed
779
		if (description)
Vladimir Panteleev's avatar
Vladimir Panteleev committed
780
			node = g.addNode(kind, description.wrapNodeText, true, tooltip);
781
782
783
784
785
786
		else
		{
			stderr.writefln("Missing description for segment %s", id);
			node = g.addNode(kind, id, false, tooltip);
		}
		segmentNodes[id] = node;
787
	}
788
789
	foreach (id, data; video.segmentGroups)
		segmentGroupNodes[id] = g.addNode(NodeKind.segmentGroup, "sg_" ~ id);
790
	g.firstNode = segmentNodes[segmentMap.initialSegment];
791

792
	bool[string] findPreconditionVars(JSONValue json)
793
	{
794
		bool[string] seenVars;
795
796
797
798
799
		void scan(JSONValue v)
		{
			if (v.type == JSONType.array)
			{
				if (v[0].str == "persistentState")
800
					seenVars[v[1].str] = true;
801
802
803
804
805
806
				else
					foreach (c; v.array[1..$])
						scan(c);
			}
		}
		scan(json);
807
		return seenVars;
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
	}

	static JSONValue evalPrecondition(JSONValue json, scope JSONValue delegate(string) getPersistentState)
	{
		JSONValue eval(JSONValue v)
		{
			if (v.type == JSONType.false_ || v.type == JSONType.true_ || v.type == JSONType.string)
				return v;
			else
			if (v.type == JSONType.array)
				switch (v.array[0].str)
				{
					case "persistentState":
						assert(v.array.length == 2);
						return getPersistentState(v[1].str);
					case "not":
						assert(v.array.length == 2);
						return JSONValue(!eval(v[1]).boolean);
					case "and":
						return JSONValue(v.array[1..$].map!(c => eval(c).boolean).all);
					case "or":
						return JSONValue(v.array[1..$].map!(c => eval(c).boolean).any);
					case "eql":
						assert(v.array.length == 3);
						return JSONValue(eval(v[1]) == eval(v[2]));
					default:
						assert(false);
				}
			else
				assert(false);
		}
		return eval(json);
	}

842
843
844
845
846
847
848
	static ref T cached(T, Keys...)(scope T delegate() calculate, auto ref Keys keys)
	{
		static struct CacheKey { Keys keys; }
		static T[CacheKey] cache;
		return cache.require(CacheKey(keys), calculate());
	}

849
	Node[][] generateDecisionTree(Outcome)(string[] vars, size_t numOutcomes, scope Outcome delegate(JSONValue[] values) evalOutcome, Node[] parents)
850
	{
851
		JSONValue[][] varValues = vars.map!(var => allVariableValues[var].keys.sort.map!parseJSON.array).array;
852
		auto numCombinations = varValues.map!(values => values.length).fold!((a, b) => a * b)(size_t(1));
853

854
855
		auto results = cached({
			auto results = new Outcome[numCombinations];
856
			{
857
858
859
				auto currentValues = new JSONValue[vars.length];

				foreach (combination; 0 .. numCombinations)
860
				{
861
862
863
864
865
866
867
868
869
870
871
					auto rem = combination;
					// Incrementing combination index should mutate last variables,
					// so iterate in reverse order.
					foreach_reverse (varIndex, ref value; currentValues)
					{
						auto numValues = varValues[varIndex].length;
						auto valueIndex = rem % numValues;
						value = varValues[varIndex][valueIndex];
						rem /= numValues;
					}
					results[combination] = evalOutcome(currentValues);
872
873
				}
			}
874
875
			return results;
		}, vars, numOutcomes); // TODO: this cache key is probably unsound (hidden state behind evalOutcome not in cache key)..
876

877
		auto outcomes = new Node[][numOutcomes];
878

879
		void gen(uint varIndex, Node[] parents, immutable Outcome[] slice)
880
881
882
883
884
885
886
887
888
889
890
		{
			if (varIndex == vars.length)
			{
				assert(slice.length == 1);
				outcomes[slice[0]] ~= parents;
			}
			else
			{
				auto numValues = varValues[varIndex].length;
				assert(slice.length % numValues == 0);

891
				size_t[][Outcome[]] subslices;
892
893
894
895
896
897
898
899
900
901
902
903
				auto subsliceSize = slice.length / numValues;

				foreach (valueIndex; 0 .. numValues)
				{
					auto subslice = slice[valueIndex * subsliceSize .. (valueIndex + 1) * subsliceSize];
					subslices[subslice] ~= valueIndex;
				}

				if (subslices.length == 1)
				{
					// This variable is irrelevant (all possibilities
					// lead to the same outcome). No nodes generated.
904
					gen(varIndex + 1, parents, cast(immutable)subslices.byKey.front);
905
906
907
				}
				else
				{
908
909
910
911
912
					auto varName = vars[varIndex];
					Node varNode;
					if (varName in textData.vars && textData.vars[varName].readText)
						varNode = g.addNode(NodeKind.precondition, textData.vars[varName].readText.wrapNodeText, true, varName);
					else
913
						varNode = g.addNode(NodeKind.precondition, varName ~ "?");
914

915
916
917
918
919
920
921
					foreach (parent; parents)
						g.addEdge(EdgeKind.normal, parent, varNode);

					// Sort by a subslice group's first value index
					foreach (pair; subslices.byPair.array.sort!((a, b) => a[1][0] < b[1][0]))
					{
						Node[] valueNodes;
922
						if (pair[1].all!(valueIndex => varValues[varIndex][valueIndex].type.among(JSONType.true_, JSONType.false_)))
923
						{
924
							foreach (valueIndex; pair[1])
925
							{
926
927
								auto value = varValues[varIndex][valueIndex];
								auto valueNode = g.addNode(NodeKind.dummy, null);
928
								g.addEdge(value.boolean ? EdgeKind.yes : EdgeKind.no, varNode, valueNode);
929
								valueNodes ~= valueNode;
930
							}
931
932
933
						}
						else
						{
934
935
936
937
938
							auto label = pair[1]
								.map!(valueIndex => varValues[varIndex][valueIndex].toString)
								.map!(varValue => textData.vars.get(varName, TextData.Var.init).readValueText.get(varValue, varValue))
								.join(" / ");
							auto valueNode = g.addNode(NodeKind.preconditionResult, label, true);
939
940
							g.addEdge(EdgeKind.normal, varNode, valueNode);
							valueNodes = [valueNode];
941
942
943
944
945
946
947
948
949
						}
						gen(varIndex + 1, valueNodes, cast(immutable)pair[0]);
					}
				}
			}
		}
		gen(0, parents, cast(immutable)results);

		return outcomes;
950
951
	}

952
953
954
955
956
	// Returns "false" and "true" outcome branches.
	Node[][2] dumpPrecondition(JSONFragment precondition, Node[] parents)
	{
		auto json = parseJSON(precondition.json);
		auto seenVars = findPreconditionVars(json);
957
		auto vars = varReadOrder.filter!(var => var in seenVars).array;
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975

		bool evalOutcome(JSONValue[] values)
		{
			JSONValue getVar(string varName)
			{
				auto varIndex = vars.countUntil(varName);
				assert(varIndex >= 0);
				return values[varIndex];
			}

			return evalPrecondition(json, &getVar).boolean;
		}

		auto outcomes = generateDecisionTree(vars, 2, &evalOutcome, parents);
		assert(outcomes.length == 2);
		return outcomes[0..2];
	}

976
977
	Node[] dumpImpressionData(ref ImpressionData impressionData, Node[] parents)
	{
978
		if (impressionData.data.persistent == video.stateHistory)
979
		{
980
			auto impressionNode = g.addNode(NodeKind.impression, "[reset all variables]");
981
			foreach (parent; parents)
982
				g.addEdge(EdgeKind.segment, parent, impressionNode);
983
984
			return [impressionNode];
		}
985

986
		foreach (k; varWriteOrder)
987
		{
988
989
990
991
992
			auto pv = k in impressionData.data.persistent;
			if (!pv)
				continue;
			auto v = *pv;

993
994
995
996
997
998
999
1000
			Node impressionNode;
			auto value = v.json.strip;
			auto tooltip = format("%s := %s", k, v.json.strip);
			if (k in textData.vars && value in textData.vars[k].writeValueText)
				impressionNode = g.addNode(NodeKind.impression, textData.vars[k].writeValueText[value].wrapNodeText, true, tooltip);
			else
				impressionNode = g.addNode(NodeKind.impression, tooltip);

For faster browsing, not all history is shown. View entire blame