about summary refs log tree commit diff stats
path: root/cpp/000organization
blob: 6c51380909bc7327ef6704b0cd0b49d788ed10ca (plain) (blame)
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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
//: You guessed right: the '000' prefix means you should start reading here.
//:
//: This project is setup to load all files with a numeric prefix. Just create
//: a new file and start hacking.
//:
//: The first few files (00*) are independent of what this program does, an
//: experimental skeleton that will hopefully make it both easier for others to
//: understand and more malleable, easier to rewrite and remould into radically
//: different shapes without breaking in subtle corner cases. The premise is
//: that understandability and rewrite-friendliness are related in a virtuous
//: cycle. Doing one well makes it easier to do the other.
//:
//: Lower down, this file contains a legal, bare-bones C++ program. It doesn't
//: do anything yet; subsequent files will add behaviors by inserting lines
//: into it with directives like:
//:   :(after "more events")
//: This will insert the following lines after a line in the program containing
//: the words "more events".
//: A simple tool will 'tangle' these files according to the directives, though
//: it'll drop these comments starting with a '//:' prefix that only make sense
//: in the context of layers.
//:
//: Directives free up the programmer to order code for others to read rather
//: than as forced by the computer or compiler. Each individual feature can be
//: organized in a self-contained 'layer' that adds code to many different data
//: structures and functions all over the program. The right decomposition into
//: layers will let each layer make sense in isolation.
//:
//:   "If I look at any small part of it, I can see what is going on -- I don't
//:   need to refer to other parts to understand what something is doing.
//:
//:   If I look at any large part in overview, I can see what is going on -- I
//:   don't need to know all the details to get it.
//:
//:   Every level of detail is as locally coherent and as well thought-out as
//:   any other level."
//:
//:       -- Richard Gabriel, "The Quality Without A Name"
//:          (http://dreamsongs.com/Files/PatternsOfSoftware.pdf, page 42)
//:
//: Directives are powerful; they permit inserting or modifying any point in
//: the program. Using them tastefully requires mapping out specific lines as
//: waypoints for future layers to hook into. Often such waypoints will be in
//: comments, capitalized to hint that other layers rely on their presence.
//:
//: A single waypoint might have many different code fragments hooking into
//: it from all over the codebase. Use 'before' directives to insert
//: code at a location in order, top to bottom, and 'after' directives to
//: insert code in reverse order. By convention waypoints intended for insertion
//: before begin with 'End'. Notice below how the layers line up above the "End
//: Foo" waypoint.
//:
//:   File 001          File 002                File 003
//:   ============      ===================     ===================
//:   // Foo
//:   ------------
//:              <----  :(before "End Foo")
//:                     ....
//:                     ...
//:   ------------
//:              <----------------------------  :(before "End Foo")
//:                                             ....
//:                                             ...
//:   // End Foo
//:   ============
//:
//: Here's part of a layer in color: http://i.imgur.com/0eONnyX.png. Directives
//: are shaded dark. Notice the references to waypoints lower down in this
//: file.
//:
//: Layers do more than just shuffle code around. Past the initial skeleton of
//: this program (currently 00*-02*), it ought to be possible to stop loading
//: after any file/layer, build and run the program, and pass all tests for
//: loaded features. (Relevant is http://youtube.com/watch?v=c8N72t7aScY, a
//: scene from "2001: A Space Odyssey".)
//:
//: This 'subsetting guarantee' ensures that this directory contains a
//: cleaned-up narrative of the evolution of this codebase. Organizing
//: autobiographically allows a newcomer to rapidly orient himself, reading the
//: first few files to understand a simple gestalt of a program's core purpose
//: and features, and later gradually working his way through other features as
//: the need arises. Each step should be as simple as possible (but no simpler).
//:
//: Programmers shouldn't need to understand everything about a program to hack
//: on it. But they shouldn't be prevented from a thorough understanding of
//: each aspect either. The goal of layers is to reward curiosity.

// Includes
// End Includes

// Types
// End Types

// prototypes are auto-generated; define your functions in any order
#include "function_list"  // by convention, files ending with '_list' are auto-generated

// Globals
// End Globals

int main(int argc, char* argv[]) {
  return 0;  // End Main
}

void setup() {
  // End Setup
}

//: Without directives or with the :(code) directive, lines get added at the
//: end.
/ccgtypes.nim?h=devel&id=a42545ea3eecb57eea3d02c624b91c86bdaf90e6'>a42545ea3 ^
e817d5436 ^
f25c638dc ^

a42545ea3 ^
e817d5436 ^
f25c638dc ^
e25474154 ^

22dc76a36 ^


badb6c0f6 ^







8319e2411 ^
39235e21f ^
e817d5436 ^
8319e2411 ^
e25474154 ^



8319e2411 ^


e817d5436 ^
e25474154 ^


990dc2d71 ^







e25474154 ^

b5d8e8bfa ^
f265c3e86 ^

990dc2d71 ^
51de278bd ^
f265c3e86 ^
98e5beb93 ^
badb6c0f6 ^
e25474154 ^










f265c3e86 ^
e25474154 ^
990dc2d71 ^

51de278bd ^
e25474154 ^
f265c3e86 ^

632aece19 ^
f265c3e86 ^

e2d38a57e ^
e25474154 ^















f265c3e86 ^
e25474154 ^










f265c3e86 ^


e25474154 ^











e817d5436 ^
e25474154 ^

e817d5436 ^
e25474154 ^

dce8949b9 ^
2f066395b ^
e4c432387 ^

e25474154 ^
dce8949b9 ^
e25474154 ^







03ba0f3e2 ^
e25474154 ^


e817d5436 ^
e25474154 ^




990dc2d71 ^
5c94a9e1a ^




990dc2d71 ^

e25474154 ^
161f6f722 ^
e25474154 ^

e817d5436 ^
e25474154 ^



f265c3e86 ^
22dc76a36 ^
e817d5436 ^
e25474154 ^
990dc2d71 ^
e25474154 ^
e817d5436 ^
e25474154 ^

e817d5436 ^
990dc2d71 ^

f265c3e86 ^
e25474154 ^
f265c3e86 ^
51de278bd ^
17d67ab82 ^

e25474154 ^
990dc2d71 ^
e25474154 ^

e25474154 ^
f265c3e86 ^
22dc76a36 ^
e25474154 ^



161f6f722 ^
e25474154 ^
632aece19 ^
e25474154 ^


17d67ab82 ^
e25474154 ^













e2d38a57e ^



e25474154 ^















ff02ce2d5 ^
e25474154 ^
f265c3e86 ^



e2d38a57e ^
e25474154 ^
f265c3e86 ^
e25474154 ^


f265c3e86 ^
e25474154 ^
























540e244cf ^

e25474154 ^

8aa4e4670 ^

e25474154 ^


































632aece19 ^
e25474154 ^














e25474154 ^
dce8949b9 ^
ff02ce2d5 ^
e25474154 ^
ff02ce2d5 ^
e25474154 ^

ff02ce2d5 ^

e25474154 ^

ff02ce2d5 ^

e25474154 ^


































ade67f1ab ^
e25474154 ^






51de278bd ^
990dc2d71 ^

e25474154 ^

















51de278bd ^
e25474154 ^










632aece19 ^

161f6f722 ^
632aece19 ^
e25474154 ^












e25474154 ^
8319e2411 ^





ff02ce2d5 ^

e25474154 ^



















7a249eb8c ^
e25474154 ^













b9afdffb3 ^

e25474154 ^
b9afdffb3 ^
e25474154 ^

d1c84328a ^

e25474154 ^

ade67f1ab ^
e25474154 ^

161f6f722 ^



















e25474154 ^












0b197ade6 ^
e25474154 ^


c3e790b1e ^
e25474154 ^
c3e790b1e ^
538b06a12 ^



c3e790b1e ^

ade67f1ab ^
e25474154 ^

abe9dfafe ^

e25474154 ^


48dd9679b ^

e25474154 ^




32aa46a88 ^



e25474154 ^
32aa46a88 ^


e25474154 ^
b20663ce1 ^



e25474154 ^

32aa46a88 ^
b20663ce1 ^
bd2d146c7 ^
e25474154 ^

8aa4e4670 ^



e25474154 ^
32aa46a88 ^

e25474154 ^





32aa46a88 ^


e25474154 ^









5b789f2da ^
4577751ba ^



5b789f2da ^









e25474154 ^
e25474154 ^

5b789f2da ^

e25474154 ^
5b789f2da ^




e25474154 ^


5b789f2da ^


e25474154 ^
e25474154 ^
5b789f2da ^



e25474154 ^

ff02ce2d5 ^
e25474154 ^
5b789f2da ^






e25474154 ^






5b789f2da ^

e25474154 ^







5b789f2da ^
e25474154 ^

5b789f2da ^
e25474154 ^

ff02ce2d5 ^
e25474154 ^



e25474154 ^

5b789f2da ^
e25474154 ^
32aa46a88 ^
e25474154 ^
18bec94e2 ^
e25474154 ^
18bec94e2 ^

e25474154 ^
18bec94e2 ^
e25474154 ^

18bec94e2 ^

e25474154 ^
e25474154 ^
632aece19 ^

ff02ce2d5 ^
e25474154 ^





32aa46a88 ^
e25474154 ^
6ff8752be ^
e25474154 ^




6ff8752be ^

e25474154 ^

6ff8752be ^


e25474154 ^

6ff8752be ^

1a8c6fb49 ^




e25474154 ^
6ff8752be ^
e25474154 ^
6ff8752be ^


e25474154 ^








32aa46a88 ^
e25474154 ^
6ff8752be ^

32aa46a88 ^
e25474154 ^




32aa46a88 ^
e25474154 ^




632aece19 ^


121d4e0fc ^
632aece19 ^
121d4e0fc ^

632aece19 ^
03ba0f3e2 ^








e25474154 ^
e25474154 ^
ddbad192a ^
4841b6390 ^




ff02ce2d5 ^

32aa46a88 ^
e25474154 ^
e605b22cc ^


e25474154 ^
48dd9679b ^
e2d38a57e ^
4841b6390 ^
632aece19 ^

4841b6390 ^
632aece19 ^
4841b6390 ^
03ba0f3e2 ^
4841b6390 ^
03ba0f3e2 ^
4841b6390 ^
32aa46a88 ^
4841b6390 ^




e25474154 ^
4841b6390 ^
7a249eb8c ^


4841b6390 ^
e25474154 ^
e605b22cc ^
03ba0f3e2 ^
e25474154 ^

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
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
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
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
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952


                               
                                         




                                                   

                        

                                                                          




















                                                          
                                    










                                                          










                                                          
                                 


                                                               
                                     



                                     




                                  
                                                             
                     
                                           

                                             
                                                         
                     
                                               


                                                                 
                             












































                                                                       
                                        
           
                                              
                         

                                 
                                            
                       
                               

                    


                                         







                                                           
                                  
                                                          
                      
 



                                                                            


                                                                               
                                                                


                                                              







                                         

                                       
                                    

                            
                                    
                                                                     
                                         
                                                                         
                                            










                                    
                                           
                          

                                                   
                                                                       
                        

                                  
                                                                         

                                  
                     















                                                                      
                                  










                                                                       


                                                                  











                                                                             
                                                  

                                  
                                                  

                                       
                                         
                           

                                         
              
              







                                                                                
                                                                            


                               
                                                    




                                                                               
                                                                        




                                                      

                                      
                                                                     
                                                                  

                                                           
                     



                                                                          
                               
                                             
                                        
                                                                       
                                                      
                                
                       

                                       
                     

                                            
                       
                                           
             
                                               

                                                         
                                      
                                                                             

                       
                                                            
                       
                                       



                                                                            
                                                     
                                       
                              


                                       
                                                                     













                                                                               



                                                          















                                                                            
                                     
                                                     



                                                           
                      
                                                                 
                                                        


                                                 
                                        
























                                                                    

                                              

                                                                   

                                                           


































                                                                               
                             














                                                                            
                           
                                                                               
                                                   
            
                                                                       

                                  

                                                                    

                     

                                                                    


































                                                                         
                                  






                                                                             
                                                                    

                                                                   

















                                                                 
                             










                                                                           

                                                  
                                               
                                    












                                                                          
                                                             





                                                             

                                                                  



















                                                                      
                                                                      













                                                         

                                                               
                                                 
       

                                                    

                   

                                                  
                          

                                        



















                                                                              












                                                     
  


                                                   
                               
                                           
                                                               



                                

                                    
                          

                                                                

                                                                              


                                                                                

                                                                               




                                                                  



                                                                  
 


                                                         
 



                                                                 

                                                                     
                           
                                
                                   

                               



                                                          
                          

                                                                          





                                                               


                                                                      









                                                           
                                                                          



                                                                       









                                                                          
                                                                      

                

                      
                                              




                                                                             


                                                                               


                                                                               
                
                                   



                                                   

                                                              
                                                   
                                                                   






                                                                 






                                                                     

                                                       







                                                                                
                                    

                                                               
                     

                                                              
                                                       



                                                                           

                                                       
                         
                                     
                                                          
 
                                                        
                                               

                           
                 
                           

                                                                                

                              
                                                                        
                                                

                                                   
                                      





                                                                             
                                                           
 
                                                       




                                                                          

                              

                                                        


                                    

                                       

                                 




                                                                         
                                                 
                                                          
                                                                                 


                               








                                                                                  
                                                                        
                                                       

                             
                                                         




                                                       
                                                                              




                                                               


                                                                  
                                             
                               

                                      
 








                                                                    
                                                  
                            
                                         




                                                            

                                
                                                         
                                           


                                               
             
                                
                                                                            
                                               

                               
                                                 
         
                                                       
                       
                                
                                   
                                                   
                                                                        




                                                       
              
                                                


                                                                         
                              
                                                     
                                               
 

                                            
#
#
#           The Nimrod Compiler
#        (c) Copyright 2012 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

# included from cgen.nim

# ------------------------- Name Mangling --------------------------------

proc mangleField(name: string): string = 
  case name[0]
  of 'a'..'z': 
    result = ""
    add(result, chr(ord(name[0]) - ord('a') + ord('A')))
  of '0'..'9', 'A'..'Z': 
    result = ""
    add(result, name[0])
  else: result = "HEX" & toHex(ord(name[0]), 2)
  for i in countup(1, len(name) - 1): 
    case name[i]
    of 'A'..'Z': 
      add(result, chr(ord(name[i]) - ord('A') + ord('a')))
    of '_': 
      nil
    of 'a'..'z', '0'..'9': 
      add(result, name[i])
    else: 
      add(result, "HEX")
      add(result, toHex(ord(name[i]), 2))

proc mangle(name: string): string = 
  when false:
    case name[0]
    of 'a'..'z': 
      result = ""
      add(result, chr(ord(name[0]) - ord('a') + ord('A')))
    of '0'..'9', 'A'..'Z': 
      result = ""
      add(result, name[0])
    else: result = "HEX" & toHex(ord(name[0]), 2)
  result = ""
  for i in countup(0, len(name) - 1): 
    case name[i]
    of 'A'..'Z': 
      add(result, chr(ord(name[i]) - ord('A') + ord('a')))
    of '_': 
      nil
    of 'a'..'z', '0'..'9': 
      add(result, name[i])
    else: 
      add(result, "HEX")
      add(result, toHex(ord(name[i]), 2))

proc isKeyword(w: PIdent): bool =
  # nimrod and C++ share some keywords
  # it's more efficient to test the whole nimrod keywords range
  case w.id
  of ccgKeywordsLow..ccgKeywordsHigh,
     nimKeywordsLow..nimKeywordsHigh,
     ord(wInline): return true
  else: return false

proc mangleName(s: PSym): PRope = 
  result = s.loc.r
  if result == nil: 
    if gCmd == cmdCompileToLLVM: 
      case s.kind
      of skProc, skMethod, skConverter, skConst, skIterator: 
        result = ~"@"
      of skVar, skForVar, skResult, skLet: 
        if sfGlobal in s.flags: result = ~"@"
        else: result = ~"%"
      of skTemp, skParam, skType, skEnumField, skModule: 
        result = ~"%"
      else: InternalError(s.info, "mangleName")
    when oKeepVariableNames:
      let keepOrigName = s.kind in skLocalVars - {skForVar} and 
        {sfFromGeneric, sfGlobal, sfShadowed} * s.flags == {} and
        not isKeyword(s.name)
      # XXX: This is still very experimental
      #
      # Even with all these inefficient checks, the bootstrap
      # time is actually improved. This is probably because so many
      # rope concatenations and are now eliminated.
      #
      # Future notes:
      # sfFromGeneric seems to be needed in order to avoid multiple
      # definitions of certain varialbes generated in transf with
      # names such as:
      # `r`, `res`
      # I need to study where these come from.
      #
      # about sfShadowed:
      # consider the following nimrod code:
      #   var x = 10
      #   block:
      #     var x = something(x)
      # The generated C code will be:
      #   NI x;
      #   x = 10;
      #   {
      #     NI x;
      #     x = something(x); // Oops, x is already shadowed here
      #   }
      # Right now, we work-around by not keeping the original name
      # of the shadowed variable, but we can do better - we can
      # create an alternative reference to it in the outer scope and
      # use that in the inner scope.
      #
      # about isCKeyword:
      # nimrod variable names can be C keywords.
      # We need to avoid such names in the generated code.
      # XXX: Study whether mangleName is called just once per variable.
      # Otherwise, there might be better place to do this.
      #
      # about sfGlobal:
      # This seems to be harder - a top level extern variable from
      # another modules can have the same name as a local one.
      # Maybe we should just implement sfShadowed for them too.
      #
      # about skForVar:
      # These are not properly scoped now - we need to add blocks
      # around for loops in transf
      if keepOrigName:
        result = s.name.s.mangle.newRope
      else:
        app(result, newRope(mangle(s.name.s)))
        app(result, ~"_")
        app(result, toRope(s.id))
    else:
      app(result, newRope(mangle(s.name.s)))
      app(result, ~"_")
      app(result, toRope(s.id))
    s.loc.r = result

proc isCompileTimeOnly(t: PType): bool =
  result = t.kind in {tyTypedesc, tyExpr}

proc containsCompileTimeOnly(t: PType): bool =
  if isCompileTimeOnly(t): return true
  if t.sons != nil:
    for i in 0 .. <t.sonsLen:
      if t.sons[i] != nil and isCompileTimeOnly(t.sons[i]):
        return true
  return false

proc typeName(typ: PType): PRope =
  result = if typ.sym != nil: typ.sym.name.s.mangle.toRope
           else: ~"TY"

proc getTypeName(typ: PType): PRope = 
  if (typ.sym != nil) and ({sfImportc, sfExportc} * typ.sym.flags != {}) and
      (gCmd != cmdCompileToLLVM): 
    result = typ.sym.loc.r
  else:
    if typ.loc.r == nil:
      typ.loc.r = if gCmd != cmdCompileToLLVM: con(typ.typeName, typ.id.toRope)
                  else: con([~"%", typ.typeName, typ.id.toRope])
    result = typ.loc.r
  if result == nil: InternalError("getTypeName: " & $typ.kind)
  
proc mapSetType(typ: PType): TCTypeKind =
  case int(getSize(typ))
  of 1: result = ctInt8
  of 2: result = ctInt16
  of 4: result = ctInt32
  of 8: result = ctInt64
  else: result = ctArray

proc mapType(typ: PType): TCTypeKind = 
  case typ.kind
  of tyNone, tyStmt: result = ctVoid
  of tyBool: result = ctBool
  of tyChar: result = ctChar
  of tySet: result = mapSetType(typ)
  of tyOpenArray, tyArrayConstr, tyArray, tyVarargs: result = ctArray
  of tyObject, tyTuple: result = ctStruct
  of tyGenericBody, tyGenericInst, tyGenericParam, tyDistinct, tyOrdinal,
     tyConst, tyMutable, tyIter, tyTypeDesc:
    result = mapType(lastSon(typ))
  of tyEnum: 
    if firstOrd(typ) < 0: 
      result = ctInt32
    else: 
      case int(getSize(typ))
      of 1: result = ctUInt8
      of 2: result = ctUInt16
      of 4: result = ctInt32
      of 8: result = ctInt64
      else: internalError("mapType")
  of tyRange: result = mapType(typ.sons[0])
  of tyPtr, tyVar, tyRef: 
    var base = skipTypes(typ.sons[0], abstractInst)
    case base.kind
    of tyOpenArray, tyArrayConstr, tyArray, tyVarargs: result = ctArray
    else: result = ctPtr
  of tyPointer: result = ctPtr
  of tySequence: result = ctNimSeq
  of tyProc: result = if typ.callConv != ccClosure: ctProc else: ctStruct
  of tyString: result = ctNimStr
  of tyCString: result = ctCString
  of tyInt..tyUInt64:
    result = TCTypeKind(ord(typ.kind) - ord(tyInt) + ord(ctInt))
  else: InternalError("mapType")
  
proc mapReturnType(typ: PType): TCTypeKind = 
  if skipTypes(typ, abstractInst).kind == tyArray: result = ctPtr
  else: result = mapType(typ)
  
proc getTypeDescAux(m: BModule, typ: PType, check: var TIntSet): PRope
proc needsComplexAssignment(typ: PType): bool = 
  result = containsGarbageCollectedRef(typ)

proc isInvalidReturnType(rettype: PType): bool = 
  # Arrays and sets cannot be returned by a C procedure, because C is
  # such a poor programming language.
  # We exclude records with refs too. This enhances efficiency and
  # is necessary for proper code generation of assignments.
  if rettype == nil: result = true
  else: 
    case mapType(rettype)
    of ctArray: 
      result = not (skipTypes(rettype, abstractInst).kind in
          {tyVar, tyRef, tyPtr})
    of ctStruct: 
      result = needsComplexAssignment(skipTypes(rettype, abstractInst))
    else: result = false
  
const 
  CallingConvToStr: array[TCallingConvention, string] = ["N_NIMCALL", 
    "N_STDCALL", "N_CDECL", "N_SAFECALL", 
    "N_SYSCALL", # this is probably not correct for all platforms,
                 # but one can #define it to what one wants 
    "N_INLINE", "N_NOINLINE", "N_FASTCALL", "N_CLOSURE", "N_NOCONV"]
  CallingConvToStrLLVM: array[TCallingConvention, string] = ["fastcc $1", 
    "stdcall $1", "ccc $1", "safecall $1", "syscall $1", "$1 alwaysinline", 
    "$1 noinline", "fastcc $1", "ccc $1", "$1"]

proc CacheGetType(tab: TIdTable, key: PType): PRope = 
  # returns nil if we need to declare this type
  # since types are now unique via the ``GetUniqueType`` mechanism, this slow
  # linear search is not necessary anymore:
  result = PRope(IdTableGet(tab, key))

proc getTempName(): PRope = 
  result = rfmt(nil, "TMP$1", toRope(backendId()))

proc getGlobalTempName(): PRope = 
  result = rfmt(nil, "TMP$1", toRope(backendId()))

proc ccgIntroducedPtr(s: PSym): bool = 
  var pt = skipTypes(s.typ, abstractInst)
  assert skResult != s.kind
  if tfByRef in pt.flags: return true
  elif tfByCopy in pt.flags: return false
  case pt.Kind
  of tyObject:
    if (optByRef in s.options) or (getSize(pt) > platform.floatSize * 2): 
      result = true           # requested anyway
    elif (tfFinal in pt.flags) and (pt.sons[0] == nil): 
      result = false          # no need, because no subtyping possible
    else: 
      result = true           # ordinary objects are always passed by reference,
                              # otherwise casting doesn't work
  of tyTuple: 
    result = (getSize(pt) > platform.floatSize*2) or (optByRef in s.options)
  else: result = false
  
proc fillResult(param: PSym) = 
  fillLoc(param.loc, locParam, param.typ, ~"Result",
          OnStack)
  if (mapReturnType(param.typ) != ctArray) and IsInvalidReturnType(param.typ): 
    incl(param.loc.flags, lfIndirect)
    param.loc.s = OnUnknown

proc getParamTypeDesc(m: BModule, t: PType, check: var TIntSet): PRope =
  when false:
    if t.Kind in {tyRef, tyPtr, tyVar}:
      var b = skipTypes(t.sons[0], abstractInst)
      if b.kind == tySet and mapSetType(b) == ctArray:
        return getTypeDescAux(m, b, check)
  result = getTypeDescAux(m, t, check)

proc genProcParams(m: BModule, t: PType, rettype, params: var PRope, 
                   check: var TIntSet, declareEnvironment=true) = 
  params = nil
  if (t.sons[0] == nil) or isInvalidReturnType(t.sons[0]): 
    rettype = ~"void"
  else: 
    rettype = getTypeDescAux(m, t.sons[0], check)
  for i in countup(1, sonsLen(t.n) - 1): 
    if t.n.sons[i].kind != nkSym: InternalError(t.n.info, "genProcParams")
    var param = t.n.sons[i].sym
    if isCompileTimeOnly(param.typ): continue
    if params != nil: app(params, ~", ")
    fillLoc(param.loc, locParam, param.typ, mangleName(param), OnStack)
    app(params, getParamTypeDesc(m, param.typ, check))
    if ccgIntroducedPtr(param): 
      app(params, ~"*")
      incl(param.loc.flags, lfIndirect)
      param.loc.s = OnUnknown
    app(params, ~" ")
    app(params, param.loc.r)
    # declare the len field for open arrays:
    var arr = param.typ
    if arr.kind == tyVar: arr = arr.sons[0]
    var j = 0
    while arr.Kind in {tyOpenArray, tyVarargs}:
      # this fixes the 'sort' bug:
      if param.typ.kind == tyVar: param.loc.s = OnUnknown
      # need to pass hidden parameter:
      appff(params, ", NI $1Len$2", ", @NI $1Len$2", [param.loc.r, j.toRope])
      inc(j)
      arr = arr.sons[0]
  if (t.sons[0] != nil) and isInvalidReturnType(t.sons[0]): 
    var arr = t.sons[0]
    if params != nil: app(params, ", ")
    app(params, getTypeDescAux(m, arr, check))
    if (mapReturnType(t.sons[0]) != ctArray) or (gCmd == cmdCompileToLLVM): 
      app(params, "*")
    appff(params, " Result", " @Result", [])
  if t.callConv == ccClosure and declareEnvironment: 
    if params != nil: app(params, ", ")
    app(params, "void* ClEnv")
  if tfVarargs in t.flags: 
    if params != nil: app(params, ", ")
    app(params, "...")
  if params == nil and gCmd != cmdCompileToLLVM: app(params, "void)")
  else: app(params, ")")
  params = con("(", params)

proc isImportedType(t: PType): bool = 
  result = (t.sym != nil) and (sfImportc in t.sym.flags)

proc typeNameOrLiteral(t: PType, literal: string): PRope = 
  if (t.sym != nil) and (sfImportc in t.sym.flags) and (t.sym.magic == mNone): 
    result = getTypeName(t)
  else: 
    result = toRope(literal)
  
proc getSimpleTypeDesc(m: BModule, typ: PType): PRope = 
  const 
    NumericalTypeToStr: array[tyInt..tyUInt64, string] = [
      "NI", "NI8", "NI16", "NI32", "NI64",
      "NF", "NF32", "NF64", "NF128",
      "NU", "NU8", "NU16", "NU32", "NU64",]
  case typ.Kind
  of tyPointer: 
    result = typeNameOrLiteral(typ, "void*")
  of tyEnum: 
    if firstOrd(typ) < 0: 
      result = typeNameOrLiteral(typ, "NI32")
    else: 
      case int(getSize(typ))
      of 1: result = typeNameOrLiteral(typ, "NU8")
      of 2: result = typeNameOrLiteral(typ, "NU16")
      of 4: result = typeNameOrLiteral(typ, "NI32")
      of 8: result = typeNameOrLiteral(typ, "NI64")
      else: 
        internalError(typ.sym.info, "getSimpleTypeDesc: " & $(getSize(typ)))
        result = nil
  of tyString: 
    discard cgsym(m, "NimStringDesc")
    result = typeNameOrLiteral(typ, "NimStringDesc*")
  of tyCstring: result = typeNameOrLiteral(typ, "NCSTRING")
  of tyBool: result = typeNameOrLiteral(typ, "NIM_BOOL")
  of tyChar: result = typeNameOrLiteral(typ, "NIM_CHAR")
  of tyNil: result = typeNameOrLiteral(typ, "0")
  of tyInt..tyUInt64: 
    result = typeNameOrLiteral(typ, NumericalTypeToStr[typ.Kind])
  of tyRange: result = getSimpleTypeDesc(m, typ.sons[0])
  else: result = nil
  
proc getTypePre(m: BModule, typ: PType): PRope = 
  if typ == nil: result = toRope("void")
  else: 
    result = getSimpleTypeDesc(m, typ)
    if result == nil: result = CacheGetType(m.typeCache, typ)
  
proc getForwardStructFormat(): string = 
  if gCmd == cmdCompileToCpp: result = "struct $1;$n"
  else: result = "typedef struct $1 $1;$n"
  
proc getTypeForward(m: BModule, typ: PType): PRope = 
  result = CacheGetType(m.forwTypeCache, typ)
  if result != nil: return 
  result = getTypePre(m, typ)
  if result != nil: return 
  case typ.kind
  of tySequence, tyTuple, tyObject: 
    result = getTypeName(typ)
    if not isImportedType(typ): 
      appf(m.s[cfsForwardTypes], getForwardStructFormat(), [result])
    IdTablePut(m.forwTypeCache, typ, result)
  else: InternalError("getTypeForward(" & $typ.kind & ')')
  
proc mangleRecFieldName(field: PSym, rectype: PType): PRope = 
  if (rectype.sym != nil) and
      ({sfImportc, sfExportc} * rectype.sym.flags != {}): 
    result = field.loc.r
  else:
    result = toRope(mangleField(field.name.s))
  if result == nil: InternalError(field.info, "mangleRecFieldName")
  
proc genRecordFieldsAux(m: BModule, n: PNode, 
                        accessExpr: PRope, rectype: PType, 
                        check: var TIntSet): PRope = 
  var 
    ae, uname, sname, a: PRope
    k: PNode
    field: PSym
  result = nil
  case n.kind
  of nkRecList: 
    for i in countup(0, sonsLen(n) - 1): 
      app(result, genRecordFieldsAux(m, n.sons[i], accessExpr, rectype, check))
  of nkRecCase: 
    if (n.sons[0].kind != nkSym): InternalError(n.info, "genRecordFieldsAux")
    app(result, genRecordFieldsAux(m, n.sons[0], accessExpr, rectype, check))
    uname = toRope(mangle(n.sons[0].sym.name.s) & 'U')
    if accessExpr != nil: ae = ropef("$1.$2", [accessExpr, uname])
    else: ae = uname
    app(result, "union {" & tnl)
    for i in countup(1, sonsLen(n) - 1): 
      case n.sons[i].kind
      of nkOfBranch, nkElse: 
        k = lastSon(n.sons[i])
        if k.kind != nkSym: 
          sname = con("S", toRope(i))
          a = genRecordFieldsAux(m, k, ropef("$1.$2", [ae, sname]), rectype, 
                                 check)
          if a != nil: 
            app(result, "struct {")
            app(result, a)
            appf(result, "} $1;$n", [sname])
        else: 
          app(result, genRecordFieldsAux(m, k, ae, rectype, check))
      else: internalError("genRecordFieldsAux(record case branch)")
    appf(result, "} $1;$n", [uname])
  of nkSym: 
    field = n.sym
    #assert(field.ast == nil)
    sname = mangleRecFieldName(field, rectype)
    if accessExpr != nil: ae = ropef("$1.$2", [accessExpr, sname])
    else: ae = sname
    fillLoc(field.loc, locField, field.typ, ae, OnUnknown)
    appf(result, "$1 $2;$n", [getTypeDescAux(m, field.loc.t, check), sname])
  else: internalError(n.info, "genRecordFieldsAux()")
  
proc getRecordFields(m: BModule, typ: PType, check: var TIntSet): PRope = 
  result = genRecordFieldsAux(m, typ.n, nil, typ, check)

proc getRecordDesc(m: BModule, typ: PType, name: PRope, 
                   check: var TIntSet): PRope = 
  # declare the record:
  var hasField = false
  if typ.kind == tyObject: 
    if typ.sons[0] == nil: 
      if (typ.sym != nil and sfPure in typ.sym.flags) or tfFinal in typ.flags: 
        result = ropecg(m, "struct $1 {$n", [name])
      else: 
        result = ropecg(m, "struct $1 {$n#TNimType* m_type;$n", [name])
        hasField = true
    elif gCmd == cmdCompileToCpp: 
      result = ropecg(m, "struct $1 : public $2 {$n", 
                      [name, getTypeDescAux(m, typ.sons[0], check)])
      hasField = true
    else: 
      result = ropecg(m, "struct $1 {$n  $2 Sup;$n", 
                      [name, getTypeDescAux(m, typ.sons[0], check)])
      hasField = true
  else: 
    result = ropef("struct $1 {$n", [name])
  var desc = getRecordFields(m, typ, check)
  if (desc == nil) and not hasField: 
    appf(result, "char dummy;$n", [])
  else: 
    app(result, desc)
  app(result, "};" & tnl)

proc getTupleDesc(m: BModule, typ: PType, name: PRope, 
                  check: var TIntSet): PRope = 
  result = ropef("struct $1 {$n", [name])
  var desc: PRope = nil
  for i in countup(0, sonsLen(typ) - 1): 
    appf(desc, "$1 Field$2;$n", 
         [getTypeDescAux(m, typ.sons[i], check), toRope(i)])
  if (desc == nil): app(result, "char dummy;" & tnl)
  else: app(result, desc)
  app(result, "};" & tnl)

proc pushType(m: BModule, typ: PType) = 
  add(m.typeStack, typ)

proc getTypeDescAux(m: BModule, typ: PType, check: var TIntSet): PRope = 
  # returns only the type's name
  var 
    name, rettype, desc, recdesc: PRope
    n: biggestInt
    t, et: PType
  t = getUniqueType(typ)
  if t == nil: InternalError("getTypeDescAux: t == nil")
  if t.sym != nil: useHeader(m, t.sym)
  result = getTypePre(m, t)
  if result != nil: return 
  if ContainsOrIncl(check, t.id): 
    InternalError("cannot generate C type for: " & typeToString(typ)) 
    # XXX: this BUG is hard to fix -> we need to introduce helper structs,
    # but determining when this needs to be done is hard. We should split
    # C type generation into an analysis and a code generation phase somehow.
  case t.Kind
  of tyRef, tyPtr, tyVar: 
    et = getUniqueType(t.sons[0])
    if et.kind in {tyArrayConstr, tyArray, tyOpenArray, tyVarargs}: 
      # this is correct! sets have no proper base type, so we treat
      # ``var set[char]`` in `getParamTypeDesc`
      et = getUniqueType(elemType(et))
    case et.Kind
    of tyObject, tyTuple: 
      # no restriction! We have a forward declaration for structs
      name = getTypeForward(m, et)
      result = con(name, "*")
      IdTablePut(m.typeCache, t, result)
      pushType(m, et)
    of tySequence: 
      # no restriction! We have a forward declaration for structs
      name = getTypeForward(m, et)
      result = con(name, "**")
      IdTablePut(m.typeCache, t, result)
      pushType(m, et)
    else: 
      # else we have a strong dependency  :-(
      result = con(getTypeDescAux(m, et, check), "*")
      IdTablePut(m.typeCache, t, result)
  of tyOpenArray, tyVarargs: 
    et = getUniqueType(t.sons[0])
    result = con(getTypeDescAux(m, et, check), "*")
    IdTablePut(m.typeCache, t, result)
  of tyProc: 
    result = getTypeName(t)
    IdTablePut(m.typeCache, t, result)
    genProcParams(m, t, rettype, desc, check)
    if not isImportedType(t): 
      if t.callConv != ccClosure: # procedure vars may need a closure!
        appf(m.s[cfsTypes], "typedef $1_PTR($2, $3) $4;$n", 
             [toRope(CallingConvToStr[t.callConv]), rettype, result, desc])
      else:
        appf(m.s[cfsTypes], "typedef struct {$n" &
            "N_NIMCALL_PTR($2, ClPrc) $3;$n" & 
            "void* ClEnv;$n} $1;$n",
             [result, rettype, desc])
  of tySequence: 
    # we cannot use getTypeForward here because then t would be associated
    # with the name of the struct, not with the pointer to the struct:
    result = CacheGetType(m.forwTypeCache, t)
    if result == nil: 
      result = getTypeName(t)
      if not isImportedType(t): 
        appf(m.s[cfsForwardTypes], getForwardStructFormat(), [result])
      IdTablePut(m.forwTypeCache, t, result)
    assert(CacheGetType(m.typeCache, t) == nil)
    IdTablePut(m.typeCache, t, con(result, "*"))
    if not isImportedType(t): 
      if skipTypes(t.sons[0], abstractInst).kind != tyEmpty: 
        const
          cppSeq = "struct $2 : #TGenericSeq {$n"
          cSeq = "struct $2 {$n" &
                 "  #TGenericSeq Sup;$n"
        appcg(m, m.s[cfsSeqTypes],
            (if gCmd == cmdCompileToCpp: cppSeq else: cSeq) &
            "  $1 data[SEQ_DECL_SIZE];$n" & 
            "};$n", [getTypeDescAux(m, t.sons[0], check), result])
      else: 
        result = toRope("TGenericSeq")
    app(result, "*")
  of tyArrayConstr, tyArray: 
    n = lengthOrd(t)
    if n <= 0: 
      n = 1                   # make an array of at least one element
    result = getTypeName(t)
    IdTablePut(m.typeCache, t, result)
    if not isImportedType(t): 
      appf(m.s[cfsTypes], "typedef $1 $2[$3];$n", 
           [getTypeDescAux(m, t.sons[1], check), result, ToRope(n)])
  of tyObject, tyTuple: 
    result = CacheGetType(m.forwTypeCache, t)
    if result == nil: 
      result = getTypeName(t)
      if not isImportedType(t): 
        appf(m.s[cfsForwardTypes], getForwardStructFormat(), [result])
      IdTablePut(m.forwTypeCache, t, result)
    IdTablePut(m.typeCache, t, result) # always call for sideeffects:
    if t.kind != tyTuple: recdesc = getRecordDesc(m, t, result, check)
    else: recdesc = getTupleDesc(m, t, result, check)
    if not isImportedType(t): app(m.s[cfsTypes], recdesc)
  of tySet: 
    case int(getSize(t))
    of 1: result = toRope("NU8")
    of 2: result = toRope("NU16")
    of 4: result = toRope("NU32")
    of 8: result = toRope("NU64")
    else: 
      result = getTypeName(t)
      IdTablePut(m.typeCache, t, result)
      if not isImportedType(t): 
        appf(m.s[cfsTypes], "typedef NU8 $1[$2];$n", 
             [result, toRope(getSize(t))])
  of tyGenericInst, tyDistinct, tyOrdinal, tyConst, tyMutable, 
      tyIter, tyTypeDesc:
    result = getTypeDescAux(m, lastSon(t), check)
  else:
    InternalError("getTypeDescAux(" & $t.kind & ')')
    result = nil
  # fixes bug #145:
  excl(check, t.id)

proc getTypeDesc(m: BModule, typ: PType): PRope = 
  var check = initIntSet()
  result = getTypeDescAux(m, typ, check)

type
  TClosureTypeKind = enum
    clHalf, clHalfWithEnv, clFull

proc getClosureType(m: BModule, t: PType, kind: TClosureTypeKind): PRope =
  assert t.kind == tyProc
  var check = initIntSet()
  result = getTempName()
  var rettype, desc: PRope
  genProcParams(m, t, rettype, desc, check, declareEnvironment=kind != clHalf)
  if not isImportedType(t):
    if t.callConv != ccClosure or kind != clFull:
      appf(m.s[cfsTypes], "typedef $1_PTR($2, $3) $4;$n", 
           [toRope(CallingConvToStr[t.callConv]), rettype, result, desc])
    else:
      appf(m.s[cfsTypes], "typedef struct {$n" &
          "N_NIMCALL_PTR($2, ClPrc) $3;$n" & 
          "void* ClEnv;$n} $1;$n",
           [result, rettype, desc])

proc getTypeDesc(m: BModule, magic: string): PRope = 
  var sym = magicsys.getCompilerProc(magic)
  if sym != nil: 
    result = getTypeDesc(m, sym.typ)
  else: 
    rawMessage(errSystemNeeds, magic)
    result = nil

proc finishTypeDescriptions(m: BModule) = 
  var i = 0
  while i < len(m.typeStack): 
    discard getTypeDesc(m, m.typeStack[i])
    inc(i)
  
proc genProcHeader(m: BModule, prc: PSym): PRope = 
  var 
    rettype, params: PRope
  genCLineDir(result, prc.info)
  # using static is needed for inline procs
  if gCmd != cmdCompileToLLVM and lfExportLib in prc.loc.flags:
    if m.isHeaderFile:
      result.app "N_LIB_IMPORT "
    else:
      result.app "N_LIB_EXPORT "
  elif prc.typ.callConv == ccInline:
    result.app "static "
  var check = initIntSet()
  fillLoc(prc.loc, locProc, prc.typ, mangleName(prc), OnUnknown)
  genProcParams(m, prc.typ, rettype, params, check)
  # careful here! don't access ``prc.ast`` as that could reload large parts of
  # the object graph!
  appf(result, "$1($2, $3)$4", 
       [toRope(CallingConvToStr[prc.typ.callConv]), rettype, prc.loc.r, params])

# ------------------ type info generation -------------------------------------

proc genTypeInfo(m: BModule, typ: PType): PRope
proc getNimNode(m: BModule): PRope = 
  result = ropef("$1[$2]", [m.typeNodesName, toRope(m.typeNodes)])
  inc(m.typeNodes)

when false:
  proc getNimType(m: BModule): PRope = 
    result = ropef("$1[$2]", [m.nimTypesName, toRope(m.nimTypes)])
    inc(m.nimTypes)

  proc allocMemTI(m: BModule, typ: PType, name: PRope) = 
    var tmp = getNimType(m)
    appf(m.s[cfsTypeInit2], "$2 = &$1;$n", [tmp, name])

proc isObjLackingTypeField(typ: PType): bool {.inline.} =
  result = (typ.kind == tyObject) and ((tfFinal in typ.flags) and
      (typ.sons[0] == nil) or isPureObject(typ))

proc genTypeInfoAuxBase(m: BModule, typ: PType, name, base: PRope) = 
  var nimtypeKind: int
  #allocMemTI(m, typ, name)
  if isObjLackingTypeField(typ):
    nimtypeKind = ord(tyPureObject)
  else:
    nimtypeKind = ord(typ.kind)
  
  var size: PRope
  if tfIncompleteStruct in typ.flags: size = toRope"void*"
  else: size = getTypeDesc(m, typ)
  appf(m.s[cfsTypeInit3], 
       "$1.size = sizeof($2);$n" & "$1.kind = $3;$n" & "$1.base = $4;$n", 
       [name, size, toRope(nimtypeKind), base])
  # compute type flags for GC optimization
  var flags = 0
  if not containsGarbageCollectedRef(typ): flags = flags or 1
  if not canFormAcycle(typ): flags = flags or 2        
  #else MessageOut("can contain a cycle: " & typeToString(typ))
  if flags != 0: 
    appf(m.s[cfsTypeInit3], "$1.flags = $2;$n", [name, toRope(flags)])
  discard cgsym(m, "TNimType")
  appf(m.s[cfsVars], "TNimType $1; /* $2 */$n", 
       [name, toRope(typeToString(typ))])

proc genTypeInfoAux(m: BModule, typ: PType, name: PRope) = 
  var base: PRope
  if (sonsLen(typ) > 0) and (typ.sons[0] != nil): 
    base = genTypeInfo(m, typ.sons[0])
  else: 
    base = toRope("0")
  genTypeInfoAuxBase(m, typ, name, base)

proc discriminatorTableName(m: BModule, objtype: PType, d: PSym): PRope = 
  # bugfix: we need to search the type that contains the discriminator:
  var objtype = objtype
  while lookupInRecord(objtype.n, d.name) == nil:
    objtype = objtype.sons[0]
  if objType.sym == nil: 
    InternalError(d.info, "anonymous obj with discriminator")
  result = ropef("NimDT_$1_$2", [
    toRope(objType.sym.name.s), toRope(d.name.s)])

proc discriminatorTableDecl(m: BModule, objtype: PType, d: PSym): PRope = 
  discard cgsym(m, "TNimNode")
  var tmp = discriminatorTableName(m, objtype, d)
  result = ropef("TNimNode* $1[$2];$n", [tmp, toRope(lengthOrd(d.typ)+1)])

proc genObjectFields(m: BModule, typ: PType, n: PNode, expr: PRope) = 
  case n.kind
  of nkRecList: 
    var L = sonsLen(n)
    if L == 1: 
      genObjectFields(m, typ, n.sons[0], expr)
    elif L > 0: 
      var tmp = getTempName()
      appf(m.s[cfsTypeInit1], "static TNimNode* $1[$2];$n", [tmp, toRope(L)])
      for i in countup(0, L-1): 
        var tmp2 = getNimNode(m)
        appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", [tmp, toRope(i), tmp2])
        genObjectFields(m, typ, n.sons[i], tmp2)
      appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2; $1.sons = &$3[0];$n", 
           [expr, toRope(L), tmp])
    else:
      appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2;$n", [expr, toRope(L)])
  of nkRecCase: 
    assert(n.sons[0].kind == nkSym)
    var field = n.sons[0].sym
    var tmp = discriminatorTableName(m, typ, field)
    var L = lengthOrd(field.typ)
    assert L > 0
    appf(m.s[cfsTypeInit3], "$1.kind = 3;$n" &
        "$1.offset = offsetof($2, $3);$n" & "$1.typ = $4;$n" &
        "$1.name = $5;$n" & "$1.sons = &$6[0];$n" &
        "$1.len = $7;$n", [expr, getTypeDesc(m, typ), field.loc.r, 
                           genTypeInfo(m, field.typ), 
                           makeCString(field.name.s), 
                           tmp, toRope(L)])
    appf(m.s[cfsData], "TNimNode* $1[$2];$n", [tmp, toRope(L+1)])
    for i in countup(1, sonsLen(n)-1): 
      var b = n.sons[i]           # branch
      var tmp2 = getNimNode(m)
      genObjectFields(m, typ, lastSon(b), tmp2)
      case b.kind
      of nkOfBranch: 
        if sonsLen(b) < 2: 
          internalError(b.info, "genObjectFields; nkOfBranch broken")
        for j in countup(0, sonsLen(b) - 2): 
          if b.sons[j].kind == nkRange: 
            var x = int(getOrdValue(b.sons[j].sons[0]))
            var y = int(getOrdValue(b.sons[j].sons[1]))
            while x <= y: 
              appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", [tmp, toRope(x), tmp2])
              inc(x)
          else: 
            appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", 
                 [tmp, toRope(getOrdValue(b.sons[j])), tmp2])
      of nkElse: 
        appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", 
             [tmp, toRope(L), tmp2])
      else: internalError(n.info, "genObjectFields(nkRecCase)")
  of nkSym: 
    var field = n.sym
    appf(m.s[cfsTypeInit3], "$1.kind = 1;$n" &
        "$1.offset = offsetof($2, $3);$n" & "$1.typ = $4;$n" &
        "$1.name = $5;$n", [expr, getTypeDesc(m, typ), 
        field.loc.r, genTypeInfo(m, field.typ), makeCString(field.name.s)])
  else: internalError(n.info, "genObjectFields")
  
proc genObjectInfo(m: BModule, typ: PType, name: PRope) = 
  if typ.kind == tyObject: genTypeInfoAux(m, typ, name)
  else: genTypeInfoAuxBase(m, typ, name, toRope("0"))
  var tmp = getNimNode(m)
  genObjectFields(m, typ, typ.n, tmp)
  appf(m.s[cfsTypeInit3], "$1.node = &$2;$n", [name, tmp])

proc genTupleInfo(m: BModule, typ: PType, name: PRope) =
  genTypeInfoAuxBase(m, typ, name, toRope("0"))
  var expr = getNimNode(m)
  var length = sonsLen(typ)
  if length > 0: 
    var tmp = getTempName()
    appf(m.s[cfsTypeInit1], "static TNimNode* $1[$2];$n", [tmp, toRope(length)])
    for i in countup(0, length - 1): 
      var a = typ.sons[i]
      var tmp2 = getNimNode(m)
      appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", [tmp, toRope(i), tmp2])
      appf(m.s[cfsTypeInit3], "$1.kind = 1;$n" &
          "$1.offset = offsetof($2, Field$3);$n" & 
          "$1.typ = $4;$n" &
          "$1.name = \"Field$3\";$n", 
           [tmp2, getTypeDesc(m, typ), toRope(i), genTypeInfo(m, a)])
    appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2; $1.sons = &$3[0];$n", 
         [expr, toRope(length), tmp])
  else: 
    appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2;$n", 
         [expr, toRope(length)])
  appf(m.s[cfsTypeInit3], "$1.node = &$2;$n", [name, expr])

proc genEnumInfo(m: BModule, typ: PType, name: PRope) =
  # Type information for enumerations is quite heavy, so we do some
  # optimizations here: The ``typ`` field is never set, as it is redundant
  # anyway. We generate a cstring array and a loop over it. Exceptional
  # positions will be reset after the loop.
  genTypeInfoAux(m, typ, name)
  var nodePtrs = getTempName()
  var length = sonsLen(typ.n)
  appf(m.s[cfsTypeInit1], "static TNimNode* $1[$2];$n", 
       [nodePtrs, toRope(length)])
  var enumNames, specialCases: PRope
  var firstNimNode = m.typeNodes
  var hasHoles = false
  for i in countup(0, length - 1): 
    assert(typ.n.sons[i].kind == nkSym)
    var field = typ.n.sons[i].sym
    var elemNode = getNimNode(m)
    if field.ast == nil:
      # no explicit string literal for the enum field, so use field.name:
      app(enumNames, makeCString(field.name.s))
    else:
      app(enumNames, makeCString(field.ast.strVal))
    if i < length - 1: app(enumNames, ", " & tnl)
    if field.position != i or tfEnumHasHoles in typ.flags:
      appf(specialCases, "$1.offset = $2;$n", [elemNode, toRope(field.position)])
      hasHoles = true
  var enumArray = getTempName()
  var counter = getTempName()
  appf(m.s[cfsTypeInit1], "NI $1;$n", [counter])
  appf(m.s[cfsTypeInit1], "static char* NIM_CONST $1[$2] = {$n$3};$n", 
       [enumArray, toRope(length), enumNames])
  appf(m.s[cfsTypeInit3], "for ($1 = 0; $1 < $2; $1++) {$n" &
      "$3[$1+$4].kind = 1;$n" & "$3[$1+$4].offset = $1;$n" &
      "$3[$1+$4].name = $5[$1];$n" & "$6[$1] = &$3[$1+$4];$n" & "}$n", [counter, 
      toRope(length), m.typeNodesName, toRope(firstNimNode), enumArray, nodePtrs])
  app(m.s[cfsTypeInit3], specialCases)
  appf(m.s[cfsTypeInit3], 
       "$1.len = $2; $1.kind = 2; $1.sons = &$3[0];$n$4.node = &$1;$n", 
       [getNimNode(m), toRope(length), nodePtrs, name])
  if hasHoles:
    # 1 << 2 is {ntfEnumHole}
    appf(m.s[cfsTypeInit3], "$1.flags = 1<<2;$n", [name])

proc genSetInfo(m: BModule, typ: PType, name: PRope) = 
  assert(typ.sons[0] != nil)
  genTypeInfoAux(m, typ, name)
  var tmp = getNimNode(m)
  appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 0;$n" & "$3.node = &$1;$n", 
       [tmp, toRope(firstOrd(typ)), name])

proc genArrayInfo(m: BModule, typ: PType, name: PRope) = 
  genTypeInfoAuxBase(m, typ, name, genTypeInfo(m, typ.sons[1]))

proc fakeClosureType(owner: PSym): PType =
  # we generate the same RTTI as for a tuple[pointer, ref tuple[]]
  result = newType(tyTuple, owner)
  result.rawAddSon(newType(tyPointer, owner))
  var r = newType(tyRef, owner)
  r.rawAddSon(newType(tyTuple, owner))
  result.rawAddSon(r)

type
  TTypeInfoReason = enum  ## for what do we need the type info?
    tiNew,                ## for 'new'
    tiNewSeq,             ## for 'newSeq'
    tiNonVariantAsgn,     ## for generic assignment without variants
    tiVariantAsgn         ## for generic assignment with variants

include ccgtrav

proc genTypeInfo(m: BModule, typ: PType): PRope = 
  var t = getUniqueType(typ)
  result = ropef("NTI$1", [toRope(t.id)])
  let owner = typ.skipTypes(abstractPtrs).owner.getModule
  if owner != m.module:
    # make sure the type info is created in the owner module
    discard genTypeInfo(owner.bmod, typ)
    # refenrece the type info as extern here
    discard cgsym(m, "TNimType")
    discard cgsym(m, "TNimNode")
    appf(m.s[cfsVars], "extern TNimType $1; /* $2 */$n", 
         [result, toRope(typeToString(t))])
    return con("(&".toRope, result, ")".toRope)
  if ContainsOrIncl(m.typeInfoMarker, t.id):
    return con("(&".toRope, result, ")".toRope)
  case t.kind
  of tyEmpty: result = toRope"0"
  of tyPointer, tyBool, tyChar, tyCString, tyString, tyInt..tyUInt64, tyVar:
    genTypeInfoAuxBase(m, t, result, toRope"0")
  of tyProc:
    if t.callConv != ccClosure:
      genTypeInfoAuxBase(m, t, result, toRope"0")
    else:
      genTupleInfo(m, fakeClosureType(t.owner), result)
  of tySequence, tyRef:
    genTypeInfoAux(m, t, result)
    if optRefcGC in gGlobalOptions:
      let markerProc = genTraverseProc(m, t, tiNew)
      appf(m.s[cfsTypeInit3], "$1.marker = $2;$n", [result, markerProc])
  of tyPtr, tyRange: genTypeInfoAux(m, t, result)
  of tyArrayConstr, tyArray: genArrayInfo(m, t, result)
  of tySet: genSetInfo(m, t, result)
  of tyEnum: genEnumInfo(m, t, result)
  of tyObject: genObjectInfo(m, t, result)
  of tyTuple: 
    # if t.n != nil: genObjectInfo(m, t, result)
    # else:
    # BUGFIX: use consistently RTTI without proper field names; otherwise
    # results are not deterministic!
    genTupleInfo(m, t, result)
  else: InternalError("genTypeInfo(" & $t.kind & ')')
  result = con("(&".toRope, result, ")".toRope)

proc genTypeSection(m: BModule, n: PNode) = 
  nil