Generics proposals: what changed

Revision 1 to 2. Removed lines have a minus sign; added lines have a plus sign.

Old	New		Line
1	1		## Already implemented!
2	2
3	3		> Note: Generic classes are already implemented in the 2.3.1 version of FPC. See the [FPC reference](http://www.freepascal.org/docs-html/ref/ref.html).
4	4
5	5		This page contains proposals and ideas, which have lead to the current implementation and for further features.
6	6
7	7		Note, April 8th 2019: almost everything on this page is highly outdated and does not reflect the current state of FPC features.
8	8
9	9		## Why
10	10
11	11		- Typesafety !
12	12		- Speed
13	13		- Readability
14	14
15	15		See "Already existing stuff" for possible but lacking ways right now.
16	16
17	17		## Interested Parties
18	18
19	19		\- Almindor - dannym - fpk - giantm - oliebol - plugwash - Synopsis - tom - PublicJoke - neli - dr_evil
20	20
21	21		## Usage example (uncategorized)
22	22
23	23		TODO: combine the below stuff into one example using the \<\> syntax
24	24
25	25		(tom proposal)
26	26
27	27		``` pascal
28	28		type
29	29		// explicit addition of "generic" keyword. Maybe something like "uses generic <...>"
30	30		// better use the <>-brackets because otherwise it may cause confusion with arrays
31	31		// in the actual instantiation
32	32		abc = class(..) generic <a, b>
33	33		end;
34	34		var
35	35		// because they're still unused ;)
36	36		xyz : abc<String, Integer>;
37	37		xyz2 : abc<AObj1, AObj2>;
38	38		begin
39	39		// don't repeat generics in instance creation (if not necessary)
40	40		xyz := abc.Create;
41	41		xyz2 := abc<descendant_of_Aobj1, descendant_of_Aobj2>.Create;
42	42		end.
43	43		```
44	44
45	45		(dannym proposal new)
46	46
47	47		``` pascal
48	48		type
49	49		GList = generic class of T
50	50		public
51	51		procedure Add(const stuff: T);
52	52		end;
53	53
54	54		procedure GList.Add(const stuff: T); // note that here no 'of T'
55	55		begin
56	56		...
57	57		end;
58	58
59	59		var
60	60		intlist: GList of Integer;
61	61		begin
62	62		intlist := GList.Create; // note that here the detail type is missing and
63	63		// needs to be deducted from the var declaration
64	64		//or intlist := typeof(intlist).Create;
65	65		//intlist := GList of Integer.Create; <-- this is unclear if that works
66	66		end;
67	67		```
68	68
69	69		(dannym proposal - old)
70	70
71	71		``` pascal
72	72		type
73	73		GList<T> = class
74	74		public
75	75		procedure Add(const stuff: T);
76	76		end;
77	77
78	78		procedure GList<T>.Add(const stuff: T);
79	79		begin
80	80		...
81	81		end;
82	82
83	83		var
84	84		intlist: GList<Integer>;
85	85		begin
86	86		intlist := GList<Integer>.Create;
87	87		end;
88	88		```
89	89
90	90		plugwash:
91	91
92	92		``` pascal
93	93		tmycollection=template(tobject)[x]
94	94		tintegercollection=tmycollection[integer]
95	95		```
96	96
97	97		oliebol:
98	98
99	99		``` pascal
100	100		template blaat<t:integer>(a:t);
101	101		var x : t;
102	102		begin
103	103		do something with a, and use t with it
104	104		end;
105	105		```
106	106
107	107		note that we should have a generics section (like interface and implementation sections) containing the generics:
108	108
109	109		``` pascal
110	110		unit xyz;
111	111		generics
112	112		type
113	113		GList......
114	114		procedure GList.Add(const value: T);
115	115		....
116	116		end.
117	117		```
118	118
119	119		(eiffel)
120	120
121	121		<http://paste.lisp.org/display/6236>
122	122
123	123		(PublicJoke proposal)
124	124
125	125		``` pascal
126	126		unit Unit1(TMathType);
127	127
128	128		interface
129	129
130	130		type
131	131		TMathClass = class
132	132		public
133	133		class function Add(a1, a2: TMathType): TMathType;
134	134		end;
135	135
136	136		implementation
137	137
138	138		class function TMathClass.Add(a1, a2: TMathType): TMathType;
139	139		begin
140	140		Result:=a1+a2;
141	141		end;
142	142
143	143		end.
144	144		```
145	145
146	146		``` pascal
147	147		unit Unit2;
148	148
149	149		type
150	150		TMathType = Longword;
151	151
152	152		interface
153	153
154	154		implementation
155	155
156	156		end.
157	157		```
158	158
159	159		``` pascal
160	160		program prog;
161	161
162	162		uses
163	163		Unit2,
164	164		Unit1(Byte) as ByteMath in 'Unit1.pas',
165	165		Unit1(TMathType) as PolyMath in 'Unit1.pas';
166	166
167	167		type
168	168		TByteMathClass = ByteMath.TMathClass;
169	169		TPolyMathClass = PolyMath.TMathClass;
170	170
171	171		var
172	172		b: Byte;
173	173		p: TMathType;
174	174
175	175		begin
176	176		b:=TByteMathClass.Add(1, 2);
177	177		p:=TPolyMathClass.Add(3, 4);
178	178		end.
179	179		```
180	180
181	181		(Gadnio proposal) I personally think the C++ way of doing this is clear enough AND will be the easiest to parse/understand:
182	182
183	183		``` pascal
184	184		template <T>
185	185		TGenericObject< T > = record
186	186		Data : T;
187	187		OtherStuff : Pointer;
188	188		end;{TGenericObject}
189	189		template <TKey, TData = TGenericObject< boolean > >
190	190		TGenericList = class( TWhee< TKey > )
191	191		public
192	192		function Lookup( const Key : TKey ): TData;
193	193		template <THihi>
194	194		class function DataToHihi( Data : TData ): THihi;
195	195		end;{TGenericList}
196	196		```
197	197
198	198		Also, note that template specialization is a very, very important thing (for me especially). In C++ they've got vector\< bool \> that behaves different than the standard vector\< T \>. An example:
199	199
200	200		``` pascal
201	201		template <T, TT>
202	202		TSame = class
203	203		class function Same: Boolean;
204	204		end;{TSame}
205	205		template <T>
206	206		TSame = class
207	207		class function Same: Boolean;
208	208		end;{TSame}
209	209		```
210	210
211	211		``` pascal
212	212		template <T, TT>
213	213		class function TSame.Same: Boolean;
214	214		begin
215	215		Result := false;
216	216		end;{TSame<T, TT>.Same}
217	217		template <T>
218	218		class function TSame.Same: Boolean;
219	219		begin
220	220		Result := true;
221	221		end;{TSame<T>.Same}
222	222		```
223	223
224	224		This allows to make a compile-time check for same types that are not TObject, e.g.
225	225
226	226		``` pascal
227	227		TFoo = class;
228	228		TBar = class( TFoo );
229	229		var
230	230		S : Boolean;
231	231		begin
232	232		S := TSame< String, Integer >.Same; //s = false
233	233		S := TSame< Int64, Integer >.Same; //s = false
234	234		S := TSame< String, String >.Same; //s = true
235	235		S := TSame< TBar, TFoo >.Same;//s = false (not the same as "var x: TFoo; begin x := TBar.Create; end;" )
236	236		end;
237	237		```
238	238
239	239		Another thing to note: It would be very good if something like this (c++ syntax) would be implemented:
240	240
241	241		``` pascal
242	242		template <bool b>
243	243		class h
244	244		{
245	245		public:
246	246		static const int i = 0;
247	247		};//h
248	248		```
249	249
250	250		``` c
251	251		template <>
252	252		class h< true >
253	253		{
254	254		public:
255	255		static const int i = 1;
256	256		};
257	257		```
258	258
259	259		``` c
260	260		template <>
261	261		class h< false >
262	262		{
263	263		public:
264	264		static const int i = 2;
265	265		};
266	266		```
267	267
268	268		Here
269	269
270	270		``` c
271	271		h<false>.i = 2
272	272		h<true>.i = 1
273	273		```
274	274
275	275		ALWAYS.
276	276
277	277		## Usage example
278	278
279	279		If you add more syntax examples, please add equivalent to both. Two main syntaxes seem to be popular, "\<\>" which looks more or less like C++, c#, etc.. and adding a "generic" keyword which is more along the Pascal style of code. Go to [[Generics Vote]] to vote for one or the other syntax.
280	280
281	281		### Using brackets: \<\>
282	282
283	283		``` pascal
284	284		type
285	285		TGenericCollection<T: TCollectionItem> = class(TComponent)
286	286		...implement TCollection and use T
287	287		end;
288	288
289	289		TCollection = TGenericCollection<TCollectionItem>;
290	290		TFieldDefs = TGenericCollection<TFieldDef>;
291	291
292	292		TGenericList<T: PtrInt> = class(TObject)
293	293		...implement TList and use PtrInt size for code generation
294	294		end;
295	295
296	296		TList = TGenericList<Pointer>;
297	297		```
298	298
299	299		Implementation of TGenericCollection can be compiled as if (T: TCollectionItem) were used.
300	300
301	301		Would this solve the circular dependency ? It seems so to me, because one knows at least as much as in current implementation of these classes, but I'm no compiler engineer.
302	302
303	303		For procedures:
304	304
305	305		``` pascal
306	306		function MyFunc<T: TTreeItem>(A: T): T;
307	307		begin
308	308		// do something with the tree item
309	309		end;
310	310
311	311		function Max<T>(A, B: T): T;
312	312		begin
313	313		if A < B then
314	314		Result := B
315	315		else
316	316		Result := A;
317	317		end;
318	318		```
319	319
320	320		My restrictions won't allow implementing generic Max and Min, I guess. That really needs macro-alike stuff (for the compiler implementation).
321	321
322	322		Another example for linked lists: (ripped from mail to fpc-devel of dannym, but modified a bit)
323	323
324	324		``` pascal
325	325		type
326	326		TListItem<T> = record
327	327		Data: T;
328	328		Next: TListItem;
329	329		end;
330	330		PListItem = ^TListItem;
331	331
332	332		TList<T> = class
333	333		private
334	334		fHead: PListItem<T>;
335	335		fTail: PListItem<T>;
336	336		published
337	337		procedure Add(Item: T);
338	338		end;
339	339
340	340		procedure TList<T>.Add(Item: T);
341	341		var
342	342		node: PListItem<T>;
343	343		begin
344	344		New(node);
345	345		node^.Data := Item;
346	346		node^.Next := nil;
347	347
348	348		if Assigned(fTail) then begin
349	349		fTail^.Next := node;
350	350		end else begin
351	351		fHead := node;
352	352		end;
353	353
354	354		fTail := node;
355	355		end;
356	356
357	357		type
358	358		TApple = class
359	359		end;
360	360		TOrange = class
361	361		end;
362	362
363	363		TAppleList = TList<TApple>;
364	364
365	365		var
366	366		apples: TAppleList;
367	367		apple: TApple;
368	368		begin
369	369		apples.Add(TApple.Create); // works
370	370		apples.Add(TOrange.Create); // compile error
371	371
372	372		apple := apples[0]; // works
373	373		apple := apples[1]; // not applicable
374	374		apple := apples[0] as TApple; // works, but unneccessary
375	375		apple := apples[1] as TApple; // not applicable
376	376		end;
377	377		```
378	378
379	379		### Using the "generic" keyword
380	380
381	381		``` pascal
382	382		type
383	383		TGenericCollection = generic(T: TCollectionItem) class(TComponent)
384	384		...implement TCollection and use T
385	385		end;
386	386
387	387		TCollection = specialize TGenericCollection(TCollectionItem);
388	388		TFieldDefs = specialize TGenericCollection(TFieldDef);
389	389
390	390		TGenericList = generic(T: PtrInt) class(TObject)
391	391		...implement TList and use PtrInt size for code generation
392	392		end;
393	393
394	394		TList = specialize TGenericList(Pointer);
395	395		```
396	396
397	397		For procedures:
398	398
399	399		``` pascal
400	400		function generic(T: TTreeItem) MyFunc(A: T): T;
401	401		begin
402	402		// do something with the tree item
403	403		end;
404	404
405	405		function generic(T) Max(A, B: T): T;
406	406		begin
407	407		if A < B then
408	408		Result := B
409	409		else
410	410		Result := A;
411	411		end;
412	412		```
413	413
414	414		Another example for linked lists: (ripped from mail to fpc-devel of dannym, but modified a bit)
415	415
416	416		``` pascal
417	417		type
418	418		TListItem = generic(T) record
419	419		Data: T;
420	420		Next: TListItem;
421	421		end;
422	422		PListItem = ^TListItem;
423	423
424	424		TList = generic(T) class
425	425		private
426	426		fHead: specialize PListItem(T);
427	427		fTail: specialize PListItem(T);
428	428		published
429	429		procedure Add(Item: T);
430	430		end;
431	431
432	432		procedure generic(T) TList.Add(Item: T);
433	433		var
434	434		node: specialize PListItem(T);
435	435		begin
436	436		New(node);
437	437		node^.Data := Item;
438	438		node^.Next := nil;
439	439
440	440		if Assigned(fTail) then begin
441	441		fTail^.Next := node;
442	442		end else begin
443	443		fHead := node;
444	444		end;
445	445
446	446		fTail := node;
447	447		end;
448	448
449	449		type
450	450		TApple = class
451	451		end;
452	452		TOrange = class
453	453		end;
454	454
455	455		TAppleList = specialize TList(TApple);
456	456
457	457		var
458	458		apples: TAppleList;
459	459		apple: TApple;
460	460		begin
461	461		apples.Add(TApple.Create); // works
462	462		apples.Add(TOrange.Create); // compile error
463	463
464	464		apple := apples[0]; // works
465	465		apple := apples[1]; // not applicable
466	466		apple := apples[0] as TApple; // works, but unneccessary
467	467		apple := apples[1] as TApple; // not applicable
468	468		end;
469	469		```
470	470
471	471		Ugly things in need to be resolved:
472	472
473	473		``` pascal
474	474		{ a generic type "TPointer" which is a pointer to type instantiated with }
475	475		type TPointer = generic(Type) ^Type;
476	476		{ a generic type that instantiates all the enums for Type }
477	477		type TAllEnums = generic(Type)(low(Type),high(Type));
478	478		```
479	479
480	480		So, before a keyword can be real "nice" the following things need addressing:
481	481
482	482		1. Double brackets ()(), looks C-ish again
483	483		2. In math, one usually defines functions with the parameters on the left of the equal sign, not on the right
484	484
485	485		#### Suggestion 2
486	486
487	487		Inspired by idea from oliebol in combination with ugly examples, in list of const, var, type sections, add "template" section:
488	488
489	489		``` pascal
490	490		const
491	491		ThisIsAConst = 1;
492	492
493	493		type
494	494		TMyEnum = (ab, ac);
495	495
496	496		template(T: TCollectionItem)
497	497		TGenericCollection = class(TComponent)
498	498		...implement TCollection and use T
499	499		end;
500	500
501	501		type
502	502		TCollection = specialize TGenericCollection(TCollectionItem);
503	503		TFieldDefs = specialize TGenericCollection(TFieldDef);
504	504
505	505		template(T: PtrInt)
506	506		TGenericList = class(TObject)
507	507		...implement TList and use PtrInt size for code generation
508	508		end;
509	509
510	510		type
511	511		TList = specialize TGenericList(Pointer);
512	512		```
513	513
514	514		For procedures:
515	515
516	516		``` pascal
517	517		function generic(T: TTreeItem) MyFunc(A: T): T;
518	518		begin
519	519		// do something with the tree item
520	520		end;
521	521
522	522		function generic(T) Max(A, B: T): T;
523	523		begin
524	524		if A < B then
525	525		Result := B
526	526		else
527	527		Result := A;
528	528		end;
529	529		```
530	530
531	531		Another example for linked lists: (ripped from mail to fpc-devel of dannym, but modified a bit)
532	532
533	533		``` pascal
534	534		template(T)
535	535		TListItem = record
536	536		Data: T;
537	537		Next: TListItem;
538	538		end;
539	539		PListItem = ^specialize TListItem(T);
540	540
541	541		TList = class
542	542		type
543	543		PItem = specialize PListItem(T);
544	544		private
545	545		fHead: PItem;
546	546		fTail: PItem;
547	547		published
548	548		procedure Add(Item: T);
549	549		end;
550	550
551	551		...implementation...
552	552
553	553		procedure generic(T) TList.Add(Item: T);
554	554		var
555	555		node: PItem;
556	556		begin
557	557		New(node);
558	558		node^.Data := Item;
559	559		node^.Next := nil;
560	560
561	561		if Assigned(fTail) then begin
562	562		fTail^.Next := node;
563	563		end else begin
564	564		fHead := node;
565	565		end;
566	566
567	567		fTail := node;
568	568		end;
569	569
570	570		type
571	571		TApple = class
572	572		end;
573	573		TOrange = class
574	574		end;
575	575
576	576		TAppleList = specialize TList(TApple);
577	577
578	578		var
579	579		apples: TAppleList;
580	580		apple: TApple;
581	581		begin
582	582		apples.Add(TApple.Create); // works
583	583		apples.Add(TOrange.Create); // compile error
584	584
585	585		apple := apples[0]; // works
586	586		apple := apples[1]; // not applicable
587	587		apple := apples[0] as TApple; // works, but unneccessary
588	588		apple := apples[1] as TApple; // not applicable
589	589		end;
590	590		```
591	591
592	592		#### Suggestion 3
593	593
594	594		``` pascal
595	595		{ Chu Jetcheng, 2008-07-24 }
596	596
597	597		program Generics;
598	598
599	599		type
600	600		{ The compiler should maintain a global table storing each specialized type for each generic. The
601	601		`of' operator is used to create a specialization for a specified generic type. Specialized types
602	602		of the same `type layout' (no other words) point to the same entry in the table of specializations
603	603		of the specialized generic type, and thus are compatible. Generic objects and records should also
604	604		be allowed. }
605	605
606	606		TGeneric = generic class(TAncestorClass) of T1, T2
607	607		private
608	608		FData1: T1;
609	609		FData2: T2;
610	610		public
611	611		property Data1: T1 read FData1 write FData1;
612	612		property Data2: T2 read FData2 write FData2;
613	613		constructor Create(const A: T1; const B: T2);
614	614		procedure WriteData; virtual;
615	615		end;
616	616
617	617		TGenericDescendent = generic class(TGeneric of Integer, T3) of T3
618	618		private
619	619		FData3: T3;
620	620		FObjectOfSameType: TGenericDescendent of T3;
621	621		public
622	622		property Data3: T3 read FData3 write FData3;
623	623		property ObjectOfSameType: TGenericDescendent of T3 read FObjectOfSameType write FObjectOfSameType;
624	624		constructor Create(const C: T3);
625	625		procedure WriteData; override;
626	626		end;
627	627
628	628		TGenericIR = TGeneric of Integer, Real;
629	629		TGenericIRClass = class of TGenericIR;
630	630
631	631		TGenericISClass = class of (TGeneric of Integer, string);
632	632
633	633		PGenericObj = generic ^TGenericObj;
634	634		TGenericObj = generic object of T
635	635		MyField: T;
636	636		procedure WriteData;
637	637		end;
638	638
639	639		{ TGeneric }
640	640
641	641		{ Use the same syntax for method implementations as with immediate classes. }
642	642
643	643		constructor TGeneric.Create(const A: T1; const B: T2);
644	644		begin
645	645		FData1 := A;
646	646		FData2 := B;
647	647		end;
648	648
649	649		procedure TGeneric.WriteData;
650	650		begin
651	651		Writeln(FData1);
652	652		Writeln(FData2);
653	653		end;
654	654
655	655		{ TGenericDescendent }
656	656
657	657		constructor TGenericDescendent.Create(const C: T3);
658	658		begin
659	659		inherited Create(16, C);
660	660		FData3 := C;
661	661		end;
662	662
663	663		procedure TGenericDescendent.WriteData;
664	664		begin
665	665		inherited;
666	666		Writeln(FData3);
667	667		if Assigned(FObjectOfSameType) then FObjectOfSameType.WriteData;
668	668		end;
669	669
670	670		{ TGenericObj }
671	671
672	672		procedure TGenericObj.WriteData;
673	673		begin
674	674		Writeln(MyField);
675	675		end;
676	676
677	677		var
678	678		Obj1: TGeneric of Integer, Real;
679	679		Obj2, Obj3: TGenericDescendent of string;
680	680		OldStyleObj: TGenericObj of Integer;
681	681		OldStyleObjPtr: PGenericObj of Integer;
682	682
683	683		begin
684	684		Obj1 := TGeneric.Create(32, 3.14);
685	685		Obj1.WriteData;
686	686		Writeln(#9, Obj1 is TGenericIR);
687	687		Writeln(#9, Obj1 is TGenericIS);
688	688
689	689		Obj2 := TGenericDescendent.Create('Generic test.');
690	690		Obj2.WriteData;
691	691		Writeln(#9, Obj2 is TGenericIR);
692	692		Writeln(#9, Obj2 is TGenericIS);
693	693
694	694		Obj3 := TGenericDescendent.Create('Another generic test.');
695	695		Obj3.ObjectOfSameType := Obj2;
696	696		Obj3.WriteData;
697	697
698	698		Obj3.Free;
699	699		Obj2.Free;
700	700		Obj1.Free;
701	701
702	702		OldStyleObj.MyField := 100;
703	703		OldStyleObj.WriteData;
704	704
705	705		OldStyleObjPtr := New(PGenericObj of Integer);
706	706		with OldStyleObjPtr^ do begin
707	707		MyField := 202;
708	708		WriteData;
709	709		end;
710	710		Dispose(ObjStyleObjPtr);
711	711		end.
712	712		```
713	713
714	714		## Terms
715	715
716	716		type user:
717	717
718	718		- the function in the compiler that defines a variable or return type and thus 'uses a (already defined) type'.
719	719
720	720		immediate type:
721	721
722	722		- not generic and not specialized, i.e. 'normal type'
723	723
724	724		generic type:
725	725
726	726		- template for a class with some unspecified types, never to be filled in into this class type. Only by specialisation.
727	727
728	728		specialization:
729	729
730	730		- copy generic type class to new specialized type class
731	731
732	732		type parameters:
733	733
734	734		- T and Q, the unknown types for the generic TSomeGeneric\<T,Q\>
735	735
736	736		specialized type:
737	737
738	738		- a generic type with all type parameters know, written into a real class type (tree) and reused if possible
739	739
740	740		## Changes
741	741
742	742		### Changes in class/record definition representation
743	743
744	744		Each class definition representation has added fields for:
745	745
746		-	~~` - class instantiation mode`\~~
747		-	~~` 0 immediate type`\~~
748		-	~~` 1 generic type, no instantiation, just generate specialized type`\~~
749		-	~~` 2 specialized type`~~
	746	+	``` pascal
	747	+	- class instantiation mode
	748	+	0 immediate type
	749	+	1 generic type, no instantiation, just generate specialized type
	750	+	2 specialized type
	751	+	```
750	752
751		-	~~` - when mode 2:`\~~
752		-	~~` generic type uplink (XXXX, what, unitname, typename?)`\~~
753		-	~~` when mode 1:`\~~
754		-	~~` list of specialized types known so far (and where),`\~~
755		-	~~` XXXX list items`\~~
756		-	~~` when mode 0: `\~~
757		-	~~` nothing`~~
	753	+	``` pascal
	754	+	- when mode 2:
	755	+	generic type uplink (XXXX, what, unitname, typename?)
	756	+	when mode 1:
	757	+	list of specialized types known so far (and where),
	758	+	XXXX list items
	759	+	when mode 0:
	760	+	nothing
	761	+	```
758	762
759	763		### Changes in 'type user' compilation (for class/record types only)
760	764
761	765		Each class type user will have to check mode of the class type.
762	766
763	767		For the used class type, If mode is immediate
764	768
765		-	~~` - proceed as always till now.`~~
	769	+	```text
	770	+	- proceed as always till now.
	771	+	```
766	772
767	773		If mode is specialized
768	774
769		-	~~` - proceed as always till now `\~~
770		-	~~` - keep in mind the generic type for some checks later (and debugging).`~~
	775	+	``` pascal
	776	+	- proceed as always till now
	777	+	- keep in mind the generic type for some checks later (and debugging).
	778	+	```
771	779
772	780		If mode is generic, this:
773	781
774		-	~~` - check 'list of specialized types' for the type parameter to use.`\~~
775		-	~~` If there is already a specialized type, use that.`\~~
776		-	~~` (given that it is compatible with 'compile parameters' XXXX)`~~
	782	+	``` pascal
	783	+	- check 'list of specialized types' for the type parameter to use.
	784	+	If there is already a specialized type, use that.
	785	+	(given that it is compatible with 'compile parameters' XXXX)
	786	+	```
777	787
778		-	~~` - If not available, clone the generic type in the tree, and fill in the`\~~
779		-	~~` type params with the actual types to use.`\~~
780		-	~~` Generate machine code as normal.`\~~
781		-	~~` Remember the new specialized type for later in the list by the `\~~
782		-	~~` generic type and type params used.`~~
	788	+	``` pascal
	789	+	- If not available, clone the generic type in the tree, and fill in the
	790	+	type params with the actual types to use.
	791	+	Generate machine code as normal.
	792	+	Remember the new specialized type for later in the list by the
	793	+	generic type and type params used.
	794	+	```
783	795
784	796		(the generic type is best written to some ppu as parse tree so that it can be refetched for cloning somewhen. To keep it easy, initially it should be limited to having its .pas file around when wanting to use a generic)
785	797
786	798		### type params
787	799
788	800		Generics store a list of the type params (names).
789	801
790		-	~~` ('T', 'Q')`~~
	802	+	```text
	803	+	('T', 'Q')
	804	+	```
791	805
792	806		And Specializations store a list of type mappings from the real types to the type params, in the way of
793	807
794	808		``` pascal
795	809		type
796	810		T = Integer;
797	811		Q = Boolean;
798	812		```
799	813
800	814		of course these are local to this class/record specialization.
801	815
802	816		## Other things to note (for later)
803	817
804	818		### What if a method implementation depends on the type used to know how the implementation should look like ?
805	819
806	820		``` pascal
807	821		procedure GList<T is TObject>.Add(const value: T);
808	822		procedure GList<T is Integer>.Add(const value: T);
809	823		```
810	824
811	825		?
812	826
813	827		or more cryptic like
814	828
815	829		``` pascal
816	830		procedure GList<TObject>.Add(const value: T);
817	831		procedure GList<Integer>.Add(const value: T);
818	832		```
819	833
820	834		?
821	835
822	836		or like
823	837
824	838		``` pascal
825	839		procedure GList<T>.Add(const value: Integer);
826	840		procedure GList<T>.Add(const value: TObject);
827	841		```
828	842
829	843		the latter would need extra compiler support but would be nicer, overall. Potentially clashing with normal overloads though.
830	844
831	845		or as an alternative like:
832	846
833	847		``` pascal
834	848		{$IF T is TObject}
835	849		procedure GList.Add(const value:TObject);
836	850		{$ELSE}
837	851		procedure GList.Add(const value:Integer);
838	852		{$ENDIF}
839	853		```
840	854
841	855		This would also allow to define constants or records in dependency of the generic type. This could be useful for example if you can specialize a class with static or dynamic array types (like array of double) and you need a static or dynamic array of integer having the same length as the generic. Currently we can play a bit with sizeOf(T), but this has its limitations (see <http://www.lazarusforum.de/viewtopic.php?f=10&t=11915#p106921>)...
842	856
843	857		### How to do internal storage classes
844	858
845	859		``` pascal
846	860		type
847	861		PNode<T> = ^TNode<T>;
848	862		TNode<T> = record
849	863		prev,next: PNode<T>;
850	864		data: T;
851	865		end;
852	866
853	867		type
854	868		GList<T> = class
855	869		private
856	870		head, tail: PNode<T>;
857	871		cnt: Integer;
858	872		public
859	873		procedure Add(const stuff: T);
860	874		end;
861	875		```
862	876
863	877		?
864	878
865	879		This implies that generics are best implemented both for records and for classes alike! Also implies that pointer types need to support generic too.
866	880
867	881		Also one specialization should chain other specializations (probably also when deriving from a generic).
868	882
869	883		### How to derive from the generic type
870	884
871	885		It would be good if generic types could be derived from.
872	886
873	887		``` pascal
874	888		type
875	889		TGenericEventyList<T> = class(TGenericList<T>)
876	890		public
877	891		procedure Add(value: T); override;
878	892		end;
879	893		...
880	894		```
881	895
882	896		### Interfaces should support generics too
883	897
884	898		``` pascal
885	899		type
886	900		IBa<T> = interface
887	901		procedure Add(value: T);
888	902		end;
889	903		TBa<T> = class(...,IBla<T>,IInterface)
890	904		end;
891	905		```
892	906
893	907		(what to do about the guids of the specializations? probably just generate whatever, they dont have any real meaning after all)
894	908
895	909		Of course this has limitations to check, like
896	910
897	911		- the generic interface cannot be used, just its specializations
898	912		- the specialized interface cannot be used in a generic class interface list
899	913		- (the generic interface can be used in a generic class interface list)
900	914		- the generic interface itself is invalid to use anywhere (just as generic classes are) except for specializing and deriving from
901	915		- normal interfaces cannot derive from generic interfaces
902	916		- (generic interfaces can derive from generic interfaces) - given the type params are the same
903	917		- specialized interfaces cannot be derived from
904	918
905	919		### Limitation of possible specialisations
906	920
907	921		``` pascal
908	922		type
909	923		TGenericList<T: TObject or Integer> = ...
910	924		end;
911	925		```
912	926
913	927		Probably useful...
914	928
915	929		### What to do with class functions
916	930
917	931		I dont know a whole lot of how class functions are stored internally. What happens to class functions in generics?
918	932
919	933		### 'class of'
920	934
921	935		\<Almindor\> don't forget class of, we need class of compatibility for dynamic class factories
922	936
923	937		\<Almindor\> There are possible problems with 'class of'
924	938
925	939		## Implementation details
926	940
927	941		### Sanity checks
928	942
929	943		- Generic types cannot be instantiated from
930	944		- (Generic types can be derived from)
931	945		- Specialized types cannot be derived from
932	946		- Normal types cannot use generic types in its definition
933	947		- (Normal types can use specialized types in its definition)
934	948		- There are no half specialized types (one type param specified, the other not)
935	949		- prevent loops while 'unpacking' specializations (loop counter field in every specialization)
936	950
937	951		### Things to note and not forgot
938	952
939	953		- A class and record generic can use itself as type within its definition.
940	954
941	955		example:
942	956
943	957		``` pascal
944	958		type
945	959		TBla<T> = class
946	960		parent: TBla<T>;
947	961		end;
948	962		```
949	963
950	964		- A class and record generic can use other generics as types within its definition.
951	965
952	966		``` pascal
953	967		type
954	968		TBla<T> = class
955	969		parent: TBlo<T>;
956	970		end;
957	971		```
958	972
959	973		## Implementation steps
960	974
961	975		### Extend parser to support '\<T\>' and '\<T: bla or bla or bla\>' and '\<T,Q\>' notation
962	976
963	977		Easy to do. Done.
964	978
965	979		## Different ways to do it, one excluding the other
966	980
967	981		### Way 1
968	982
969	983		#### Change class/record/object/pointertype/interface parser to mark if it is a generic, a specialization or normal
970	984
971	985		Mediate to do. Have done it for class/object and pointertype. Needs all kinds of clone functions for the defs and syms. fpk says he has patches. waiting.
972	986
973	987		#### insert dummy symbols (typesym + typedef) for the type params in the generic
974	988
975	989		Cannot be inserted into the object because parsing of types within objects has been disabled to make that possible:
976	990
977	991		``` pascal
978	992		type
979	993		Row = Cardinal;
980	994		TBla = class
981	995		Row: Integer;
982	996		end;
983	997		```
984	998
985	999		weird.. (function searchsym_type, is not possible to have type definitions in records, objects, parameters)
986	1000
987	1001		#### parse implementation section methods for the generic
988	1002
989	1003		Is harder than it sounds, because the class/object the method is member of has to be searched for the type symbol for the type params (and these not derefed but just used as is).
990	1004
991	1005		#### when parsing generics, use a dummy type in place of the type params
992	1006
993	1007		For that, defer the type checking of the compiler in that case to 'as late as possible' or 'never for the generic' \<--- TODO... hard...
994	1008
995	1009		#### Change derivation handlers to do the sanity checks
996	1010
997	1011		Should pose no problems other than finding all the places.
998	1012
999	1013		#### Add error messages for it
1000	1014
1001	1015		#### Change pexpr (tnode creating)
1002	1016
1003	1017		\<Synopsis+\> see the do_resulttypepass() calls in pexpr.pas But the compiler needs to known for example if it allows a . after the type
1004	1018
1005	1019		- add a new tnode type for postfix operators (instead of resolving the operators into the fields/methods they reference) and defer type checking until later (just before binary generation - which is not done for the generic type).
1006	1020
1007	1021		Examples for postfix operators are:
1008	1022
1009	1023		- '\[\]' array member access (normal array, class default array property?)
1010	1024
1011	1025		- '.' record/class member method/variable access
1012	1026
1013	1027		- '^' pointer dereference
1014	1028
1015	1029		- (automatic pointer dereference)
1016	1030
1017	1031		\<Synopsis\> grep for m_auto and you'll find the places where it is used \<Synopsis\> only in pexpr.pas
1018	1032
1019	1033		#### Change ppu streaming routines to save the tree of generics to the ppu
1020	1034
1021	1035		#### Change type user to instantiate specialized types for generics when used
1022	1036
1023	1037		Somewhat hard to do. (main work here :))
1024	1038
1025	1039		For the instantiation
1026	1040
1027	1041		- there is a dummy type sym needed (ok),
1028	1042		- a new objectdef
1029	1043		- clone of all the syms and defs (at least proc and property) of the original class/object
1030	1044		- and replacing all the type params by the correct types.
1031	1045		- Store that into the module as def (not on disk).
1032	1046		- (\<Synopsis+\> an additional symtable shall be added to tmodule: tempsymtable; all temporary tdef's shall be stored in that symtable)
1033	1047		- Then resume compiling for the class/object.
1034	1048
1035	1049		### Way 2
1036	1050
1037	1051		just keep the source code of the generic around and do blind replacing of the type params and then compile a specialization from that as 'source'
1038	1052
1039	1053		#### Notes
1040	1054
1041	1055		\<Synopsis+\> but the code to generate the specialization at runtime can be generated at the time the specialization is created. It doesn't need to be stored in ppu. all information is available to generate the tree at that time.
1042	1056
1043	1057		\<Synopsis+\> In the 2.1.x development series a rewrite of the ppu loading is planned to make it more clean and more maintainable. Currently it is risky to fix bugs without introducing new bugs
1044	1058
1045	1059		\<plugwash-\> It needs to be stored in some form so that the specialisations can be generated from it. \<Synopsis+\> but you can't store them in the ppu. Or with the same limitations as inlining. No references to the implementation symtable.
1046	1060
1047	1061		fpk has patches to make cloning defs possible.
1048	1062
1049	1063		01:28:24 \<Synopsis+\> users will complain; things like:
1050	1064
1051	1065		``` pascal
1052	1066		interface
1053	1067		generictype declar
1054	1068		implementation
1055	1069		procedure helper;
1056	1070		begin
1057	1071		end
1058	1072		constructor generictype.create
1059	1073		begin
1060	1074		helper
1061	1075		end
1062	1076		end.
1063	1077		```
1064	1078
1065	1079		Will not be allowed.
1066	1080
1067	1081		Another problem:
1068	1082
1069	1083		``` pascal
1070	1084		unit a;
1071	1085		interface
1072	1086		generictypeA
1073	1087		implementation
1074	1088		uses B
1075	1089		end.
1076	1090
1077	1091		unit b;
1078	1092		interface
1079	1093		uses a
1080	1094		implemenation
1081	1095		begin
1082	1096		generictypeA<integer>.craete
1083	1097		end.
1084	1098		```
1085	1099
1086	1100		At the time that the implementation of B is parsed it needs already the code of generictypeA. but that is not yet parsed! The compiler doesn't know anything yet. It only knows that generictypeA exists.
1087	1101
1088	1102		\<fpk-\> dannym, Synopsis: we can simply forbid such code in generics which cause the problem
1089	1103
1090	1104		\<fpk-\> i.e. everything used by generics must be already included in the interface uses clause ... or forbid references to units used only in the implementation section :)
1091	1105
1092	1106		\<Synopsis+\> fpk had a good idea that can solve some of the issues: unit bla; interface ... generics ... implementation ... initialisation ... finalizatrion end.
1093	1107
1094	1108		\<Synopsis+\> The generics delcarations shall be put in a separate section before implementation is parsed
1095	1109
1096	1110		\<dannym\> at 'procedure TTest.Add(x: T);', T needs to be known. but it doesnt seem that the object symtable is searched for the class method parameters. correct ?
1097	1111
1098	1112		\<Synopsis+\> dannym: correct, object symtables can not contain types, because that created problems. there is special code for that: remove the objectsymtable before parsing type declarations.
1099	1113
1100	1114		``` pascal
1101	1115		{ for records, don't search the recordsymtable for the symbols of the types }
1102	1116		oldsymtablestack:=symtablestack;
1103	1117		symtablestack:=symtablestack.next;
1104	1118		```
1105	1119
1106	1120		Because you can have a field with the same name as a type
1107	1121
1108	1122		``` pascal
1109	1123		type
1110	1124		Wrd = Word;
1111	1125		R = Record
1112	1126		Wrd : Wrd;
1113	1127		end
1114	1128		```
1115	1129
1116	1130		this is allowed. To support this the record or object symtable is remvoed from the symtablestack when the type is parsed.
1117	1131
1118	1132		## Already existing stuff
1119	1133
1120	1134		### metaclasses
1121	1135
1122	1136		``` pascal
1123	1137		type
1124	1138		TObjectClass = class of TObject;
1125	1139		TTypedList = class
1126	1140		private
1127	1141		Fwanttype: TObjectClass;
1128	1142		...
1129	1143		public
1130	1144		constructor Create(itemtype: TObjectClass);
1131	1145		procedure Add(item: TObject);
1132	1146		...
1133	1147		end;
1134	1148		constructor TTypedList.Create(itemtype: TObjectClass);
1135	1149		begin
1136	1150		Fwanttype := itemtype;
1137	1151		...
1138	1152		end;
1139	1153		procedure TTypedList.Add(item: TObject);
1140	1154		begin
1141	1155		assert(item.Class = Fwanttype);
1142	1156		...
1143	1157		end;
1144	1158
1145	1159		...
1146	1160		TSomeStuff = class
1147	1161		end;
1148	1162		...
1149	1163		Flist := TTypedList.Create(TSomeStuff);
1150	1164		```
1151	1165
1152	1166		Advantages
1153	1167
1154	1168		- already works
1155	1169
1156	1170		Disadvantages
1157	1171
1158	1172		- slow at runtime
1159	1173		- cannot do simple types
1160	1174		- need to cast all the time even for the supported types (i.e. when reading). eeek.
1161	1175
1162	1176		## To be incorporated here
1163	1177
1164	1178		### Chat logs
1165	1179
1166	1180		\<Synopsis\> <http://www.eleforum.com/cgi-bin/eleweb_lift?action=3&script=wall&num=18&reversesort=true&type=today&starttime=00:00&endtime=23:59&startdate=01-02-05&enddate=01-02-05> \<Synopsis\> or \<Synopsis\> <http://neli.hopto.org:3980/~micha/irc-fpc/2005/01/%23fpc.20050102.log>
1167	1181
1168	1182		## See also
1169	1183
1170	1184		- [[Generics]]
1171	1185
1172	1186		---
1173	1187		From the Free Pascal wiki, page "Generics proposals", as it stood on 2020-02-16 after a change by GAN, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).
1174	1188		Category: FPC
1175	1189		Category: Proposals

Back to history