This repository has been archived by the owner on Jan 12, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 172
/
SimulationCode.fs
2116 lines (1755 loc) · 91.1 KB
/
SimulationCode.fs
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
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
namespace Microsoft.Quantum.QsCompiler.CsharpGeneration
open Microsoft.Quantum.QsCompiler.Transformations.SearchAndReplace
open System.IO
#nowarn "46" // Backticks removed by Fantomas: https://github.com/fsprojects/fantomas/issues/2034
open System
open System.Collections.Generic
open System.Collections.Immutable
open System.Linq
open System.Reflection
open System.Text.RegularExpressions
open Microsoft.CodeAnalysis
open Microsoft.CodeAnalysis.CSharp.Syntax
open Microsoft.CodeAnalysis.Formatting
open Microsoft.Quantum.RoslynWrapper
open Microsoft.Quantum.QsCompiler
open Microsoft.Quantum.QsCompiler.DataTypes
open Microsoft.Quantum.QsCompiler.ReservedKeywords
open Microsoft.Quantum.QsCompiler.SyntaxTokens
open Microsoft.Quantum.QsCompiler.SyntaxTree
open Microsoft.Quantum.QsCompiler.SyntaxExtensions
open Microsoft.Quantum.QsCompiler.Transformations.Core
open Microsoft.Quantum.QsCompiler.Transformations.BasicTransformations
/// ---------------------------------------------------------------------------
/// The code generation for the simulation runtime. C# code
/// for Quantum simulation is generated using the Roslyn compiler.
/// It uses BrightSword's (John Azariah's) F# wrapper for easier readability.
/// ---------------------------------------------------------------------------
module SimulationCode =
open System.Globalization
type CodegenContext with
member this.setCallable(op: QsCallable) =
{ this with current = (Some op.FullName); signature = (Some op.Signature) }
member this.setUdt(udt: QsCustomType) =
{ this with current = (Some udt.FullName) }
let autoNamespaces (context: CodegenContext) =
[
yield "System"
yield "Microsoft.Quantum.Core"
yield "Microsoft.Quantum.Intrinsic"
yield "Microsoft.Quantum.Intrinsic.Interfaces"
yield "Microsoft.Quantum.Simulation.Core"
]
let funcsAsProps =
[
("Length", { Namespace = "Microsoft.Quantum.Core"; Name = "Length" })
("Start", { Namespace = "Microsoft.Quantum.Core"; Name = "RangeStart" })
("End", { Namespace = "Microsoft.Quantum.Core"; Name = "RangeEnd" })
("Step", { Namespace = "Microsoft.Quantum.Core"; Name = "RangeStep" })
]
let internal userDefinedName (parent: QsQualifiedName option) name =
let isReserved =
match name with
| "Data"
| "Deconstruct"
| "Info"
| "Run" -> true
| _ -> Regex.IsMatch(name, @"^Item\d+$") || parent |> Option.exists (fun current' -> name = current'.Name)
if isReserved then name + "__" else name
let isCurrentOp context n =
match context.current with
| None -> false
| Some name -> name = n
let prependNamespaceString (name: QsQualifiedName) =
name.Namespace.Replace(".", "__") + "__" + name.Name
let needsFullPath context (op: QsQualifiedName) =
let hasMultipleDefinitions () =
if context.byName.ContainsKey op.Name then context.byName.[op.Name].Length > 1 else false
let sameNamespace =
match context.current with
| None -> false
| Some n -> n.Namespace = op.Namespace
let namespaces = autoNamespaces context
if sameNamespace then false
elif hasMultipleDefinitions () then true
else not (namespaces |> List.contains op.Namespace)
let getOpName context n =
if isCurrentOp context n then Directives.Self
elif needsFullPath context n then prependNamespaceString n
else n.Name + "__"
let getTypeParameters types =
let findAll (t: ResolvedType) =
t.ExtractAll (fun item ->
match item.Resolution with
| QsTypeKind.TypeParameter tp -> seq { tp }
| _ -> Seq.empty)
types |> Seq.collect findAll |> Seq.distinctBy (fun tp -> tp.Origin, tp.TypeName) |> Seq.toList
let getAllItems itemBase t =
let rec getItems (acc: Queue<ExpressionSyntax>) current =
function
| Tuple ts ->
ts |> Seq.iteri (fun i x -> getItems acc (current <|.|> ident ("Item" + (i + 1).ToString())) x)
| _ -> acc.Enqueue current
let items = Queue()
getItems items itemBase t
items
let hasTypeParameters types = not (getTypeParameters types).IsEmpty
let justTheName context (n: QsQualifiedName) =
let name = userDefinedName None n.Name
if needsFullPath context n then n.Namespace + "." + name else name
let isGeneric context (n: QsQualifiedName) =
if context.allCallables.ContainsKey n then
let signature = context.allCallables.[n].Signature
not signature.TypeParameters.IsEmpty
else
false
let findUdt context (name: QsQualifiedName) = context.allUdts.[name]
let isUdt context (name: QsQualifiedName) = context.allUdts.TryGetValue name
let inAndOutputType (qsharpType: ResolvedType) =
match qsharpType.Resolution with
| QsTypeKind.Operation ((tIn, tOut), _) -> (tIn, tOut)
| QsTypeKind.Function (tIn, tOut) -> (tIn, tOut)
// TODO: Diagnostics
| _ -> failwith "Invalid ResolvedType for callable definition"
let hasAdjointControlled functors =
let oneFunctor (adj, ctrl) f =
match f with
| QsFunctor.Adjoint -> (true, ctrl)
| QsFunctor.Controlled -> (adj, true)
match functors with
| Value fs -> fs |> Seq.fold oneFunctor (false, false)
// TODO: Diagnostics
| Null -> (true, true)
// Maps Q# types to their corresponding Roslyn type
let rec roslynTypeName context (qsharpType: ResolvedType) : string =
match qsharpType.Resolution with
| QsTypeKind.UnitType -> "QVoid"
| QsTypeKind.Int -> "Int64"
| QsTypeKind.BigInt -> "System.Numerics.BigInteger"
| QsTypeKind.Double -> "Double"
| QsTypeKind.Bool -> "Boolean"
| QsTypeKind.String -> "String"
| QsTypeKind.Qubit -> "Qubit"
| QsTypeKind.Result -> "Result"
| QsTypeKind.Pauli -> "Pauli"
| QsTypeKind.Range -> "QRange"
| QsTypeKind.ArrayType arrayType -> sprintf "IQArray<%s>" (arrayType |> roslynTypeName context)
| QsTypeKind.TupleType tupleType -> tupleType |> roslynTupleTypeName context
| QsTypeKind.UserDefinedType name -> justTheName context (QsQualifiedName.New(name.Namespace, name.Name))
| QsTypeKind.Operation (_, functors) -> roslynCallableInterfaceName functors.Characteristics
| QsTypeKind.Function _ -> roslynCallableInterfaceName ResolvedCharacteristics.Empty
| QsTypeKind.TypeParameter t -> t |> roslynTypeParameterName
| QsTypeKind.MissingType -> "object"
// TODO: diagnostics
| QsTypeKind.InvalidType -> ""
and roslynTupleTypeName context tupleTypes =
tupleTypes |> Seq.map (roslynTypeName context) |> String.concat "," |> sprintf "(%s)"
and roslynTypeParameterName (t: QsTypeParameter) = sprintf "__%s__" t.TypeName
and roslynCallableInterfaceName characteristics =
let (adj, ctrl) = characteristics.SupportedFunctors |> hasAdjointControlled
match (adj, ctrl) with
| (true, true) -> "IUnitary"
| (true, false) -> "IAdjointable"
| (false, true) -> "IControllable"
| _ -> "ICallable"
and roslynCallableTypeName context (name: QsQualifiedName) =
if not (context.allCallables.ContainsKey name) then
userDefinedName None name.Name
else
let signature = context.allCallables.[name].Signature
let tIn = signature.ArgumentType
let tOut = signature.ReturnType
let baseInterface = roslynCallableInterfaceName signature.Information.Characteristics
if isGeneric context name then
baseInterface
else
match baseInterface with
| "ICallable" ->
sprintf "%s<%s, %s>" baseInterface (roslynTypeName context tIn) (roslynTypeName context tOut)
| _ -> sprintf "%s<%s>" baseInterface (roslynTypeName context tIn)
let isTuple =
function
| QsTypeKind.TupleType _ -> true
| _ -> false
let isCallable (qsharpType: ResolvedType) =
match qsharpType.Resolution with
| QsTypeKind.Operation _
| QsTypeKind.Function _ -> true
| _ -> false
let tupleBaseClassName context qsharpType =
let baseType = (roslynTypeName context qsharpType)
sprintf "QTuple<%s>" baseType
let udtBaseClassName context qsharpType =
let baseType = (roslynTypeName context qsharpType)
sprintf "UDTBase<%s>" baseType
// Top-level and public for testing
let floatToString (f: double) =
sprintf "%sD" (f.ToString("R", CultureInfo.InvariantCulture))
let mutable private count = 0
let private nextArgName () =
count <- count + 1
sprintf "__arg%d__" count
type ExpressionSeeker(parent: SyntaxTreeTransformation<HashSet<QsQualifiedName>>) =
inherit ExpressionTransformation<HashSet<QsQualifiedName>>(parent, TransformationOptions.NoRebuild)
override this.OnTypedExpression ex =
match ex.Expression with
| Identifier (id, _) ->
match id with
| GlobalCallable name -> this.SharedState.Add name |> ignore
| _ -> ()
| _ -> ()
base.OnTypedExpression ex
/// Used to discover which operations are used by a certain code block.
type StatementKindSeeker(parent: SyntaxTreeTransformation<HashSet<QsQualifiedName>>) =
inherit StatementKindTransformation<HashSet<QsQualifiedName>>(parent, TransformationOptions.NoRebuild)
let ALLOCATE = { Name = "Allocate"; Namespace = "Microsoft.Quantum.Intrinsic" }
let RELEASE = { Name = "Release"; Namespace = "Microsoft.Quantum.Intrinsic" }
let BORROW = { Name = "Borrow"; Namespace = "Microsoft.Quantum.Intrinsic" }
let RETURN = { Name = "Return"; Namespace = "Microsoft.Quantum.Intrinsic" }
override this.OnAllocateQubits node =
this.SharedState.Add ALLOCATE |> ignore
this.SharedState.Add RELEASE |> ignore
base.OnAllocateQubits node
override this.OnBorrowQubits node =
this.SharedState.Add BORROW |> ignore
this.SharedState.Add RETURN |> ignore
base.OnBorrowQubits node
/// Used to discover which operations are used by a certain code block.
type OperationsSeeker() as this =
inherit SyntaxTreeTransformation<HashSet<QsQualifiedName>>(HashSet(), TransformationOptions.NoRebuild)
do
this.StatementKinds <- StatementKindSeeker this
this.Expressions <- ExpressionSeeker this
this.Types <- TypeTransformation<HashSet<QsQualifiedName>>(this, TransformationOptions.Disabled)
type SyntaxBuilder(context) as this =
inherit SyntaxTreeTransformation(TransformationOptions.NoRebuild)
do
this.Namespaces <- NamespaceBuilder this
this.Statements <- StatementBlockBuilder this
this.StatementKinds <- StatementBuilder(this, context)
this.Expressions <- ExpressionTransformation(this, TransformationOptions.Disabled)
this.Types <- TypeTransformation(this, TransformationOptions.Disabled)
member val DeclarationsInStatement = LocalDeclarations.Empty with get, set
member val DeclarationsInScope = LocalDeclarations.Empty with get, set
member val BuiltStatements = [] with get, set
member val StartLine = None with get, set
member val LineNumber = None with get, set
/// Used to generate the list of statements that implement a Q# operation specialization.
and StatementBlockBuilder(parent: SyntaxBuilder) =
inherit StatementTransformation(parent, TransformationOptions.NoRebuild)
override this.OnScope(scope: QsScope) =
parent.DeclarationsInScope <- scope.KnownSymbols
base.OnScope scope
override this.OnStatement(node: QsStatement) =
match node.Location with
| Value loc ->
let current = loc.Offset.Line
parent.LineNumber <- parent.StartLine |> Option.map (fun start -> start + current + 1) // The Q# compiler reports 0-based line numbers.
| Null -> parent.LineNumber <- None // auto-generated statement; the line number will be set to the specialization declaration
parent.DeclarationsInStatement <- node.SymbolDeclarations
parent.DeclarationsInScope <-
LocalDeclarations.Concat parent.DeclarationsInScope parent.DeclarationsInStatement // only fine because/if a new statement transformation is created for every block!
base.OnStatement node
/// Used to generate the statements that implement a Q# operation specialization.
and StatementBuilder(parent: SyntaxBuilder, context) =
inherit StatementKindTransformation(parent, TransformationOptions.NoRebuild)
let withLineNumber s =
// add a line directive if the operation specifies the source file and a line number
match context.fileName, parent.LineNumber with
| Some _, Some ln when ln = 0 -> ``#line hidden`` <| s
| Some n, Some ln -> ``#line`` ln n s
| Some n, None ->
parent.StartLine
|> function
| Some ln -> ``#line`` (ln + 1) n s // we need 1-based line numbers here, and startLine is zero-based
| None -> s
| _ -> s
let QArrayType =
function
| ArrayType b -> generic "QArray" ``<<`` [ roslynTypeName context b ] ``>>`` |> Some
| _ -> None
let (|Property|_|) =
function
| CallLikeExpression (op: TypedExpression, args) ->
match op.Expression with
| Identifier (id, _) ->
match id with
| GlobalCallable n ->
funcsAsProps |> List.tryPick (fun (prop, f) -> if (n = f) then Some(args, prop) else None)
| _ -> None
| _ -> None
| _ -> None
let (|NewUdt|_|) =
function
| CallLikeExpression (op: TypedExpression, args) ->
match op.Expression with
| Identifier (id, _) ->
match id with
| GlobalCallable n when isUdt context n |> fst -> Some(n, args)
| _ -> None
| _ -> None
| _ -> None
let (|PartialApplication|_|) expression =
match expression with
| CallLikeExpression (op, args) when TypedExpression.IsPartialApplication expression -> Some(op, args)
| _ -> None
let addStatement s =
parent.BuiltStatements <- parent.BuiltStatements @ [ withLineNumber s ]
// Builds Roslyn code for a Q# expression
let rec buildExpression (ex: TypedExpression) =
match ex.Expression with
// TODO: Diagnostics
| InvalidExpr -> failwith "Can't generate code for invalid expression."
| Lambda _ -> failwith "Can't generate code for un-lifted lambda."
| UnitValue -> (ident "QVoid") <|.|> (ident "Instance")
| IntLiteral i -> literal i
| BigIntLiteral b ->
invoke
(ident "System.Numerics.BigInteger.Parse")
``(``
[ literal (b.ToString("R", CultureInfo.InvariantCulture)) ]
``)``
// otherwise converts x.0 to int, see https://stackoverflow.com/questions/24299692/why-is-a-round-trip-conversion-via-a-string-not-safe-for-a-double
| DoubleLiteral f -> ident (floatToString f) :> ExpressionSyntax
| BoolLiteral b -> upcast (if b then ``true`` else ``false``)
| ResultLiteral r ->
let name =
match r with
| Zero -> "Zero"
| One -> "One"
ident "Result" <|.|> ident name
| PauliLiteral p ->
let name =
match p with
| PauliI -> "PauliI"
| PauliX -> "PauliX"
| PauliY -> "PauliY"
| PauliZ -> "PauliZ"
ident "Pauli" <|.|> ident name
| Identifier (id, _) -> buildId id
| StringLiteral (s, e) -> buildInterpolatedString s e
| RangeLiteral (r, e) -> buildRange r e
| NEG n -> ``-`` (buildExpression n)
| NOT r -> !(buildExpression r)
| BNOT i -> Expressions.``~~~`` (buildExpression i)
| ADD (l, r) -> buildAddExpr ex.ResolvedType l r
// We use the Pow extension method from Microsoft.Quantum.Simulation.Core for all valid combinations of types.
| POW (l, r) -> invoke ((buildExpression l) <|.|> (ident "Pow")) ``(`` [ (buildExpression r) ] ``)``
| SUB (l, r) -> ``((`` ((buildExpression l) <-> (buildExpression r)) ``))``
| MUL (l, r) -> ``((`` ((buildExpression l) <*> (buildExpression r)) ``))``
| DIV (l, r) -> ``((`` ((buildExpression l) </> (buildExpression r)) ``))``
| MOD (l, r) -> ``((`` ((buildExpression l) <%> (buildExpression r)) ``))``
| EQ (l, r) -> ``((`` ((buildExpression l) .==. (buildExpression r)) ``))``
| NEQ (l, r) -> ``((`` ((buildExpression l) .!=. (buildExpression r)) ``))``
| AND (l, r) -> ``((`` ((buildExpression l) .&&. (buildExpression r)) ``))``
| OR (l, r) -> ``((`` ((buildExpression l) .||. (buildExpression r)) ``))``
| BOR (l, r) -> ``((`` ((buildExpression l) .|||. (buildExpression r)) ``))``
| BAND (l, r) -> ``((`` ((buildExpression l) .&&&. (buildExpression r)) ``))``
| BXOR (l, r) -> ``((`` ((buildExpression l) .^^^. (buildExpression r)) ``))``
| LSHIFT (l, r) -> ``((`` ((buildExpression l) .<<<. (cast "int" (buildExpression r))) ``))``
| RSHIFT (l, r) -> ``((`` ((buildExpression l) .>>>. (cast "int" (buildExpression r))) ``))``
| LT (l, r) -> ``((`` ((buildExpression l) .<. (buildExpression r)) ``))``
| LTE (l, r) -> ``((`` ((buildExpression l) .<=. (buildExpression r)) ``))``
| GT (l, r) -> ``((`` ((buildExpression l) .>. (buildExpression r)) ``))``
| GTE (l, r) -> ``((`` ((buildExpression l) .>=. (buildExpression r)) ``))``
| CONDITIONAL (c, t, f) -> ``((`` (buildConditional c t f) ``))``
| CopyAndUpdate (l, i, r) -> buildCopyAndUpdateExpression (l, i, r)
| UnwrapApplication e -> (buildExpression e) <|.|> (ident "Data")
| ValueTuple vs -> buildTuple vs
| NamedItem (ex, acc) -> buildNamedItem ex acc
| ArrayItem (a, i) -> buildArrayItem a i
| ValueArray elems -> buildValueArray ex.ResolvedType elems
| SizedArray (value, size) -> buildSizedArray value size
| NewArray (t, expr) -> buildNewArray t expr
| AdjointApplication op -> (buildExpression op) <|.|> (ident "Adjoint")
| ControlledApplication op -> (buildExpression op) <|.|> (ident "Controlled")
| Property (elem, prop) -> (buildExpression elem) <|.|> (ident prop)
| PartialApplication (op, args) -> buildPartial ex.ResolvedType ex.TypeParameterResolutions op args // needs to be before NewUdt!
| NewUdt (udt, args) -> buildNewUdt udt args // needs to be before CallLikeExpression!
| CallLikeExpression (op, args) -> buildApply ex.ResolvedType op args
| MissingExpr -> ident "_" :> ExpressionSyntax
and captureExpression (ex: TypedExpression) =
match ex.Expression with
| Identifier (s, _) when ex.InferredInformation.IsMutable ->
match ex.ResolvedType.Resolution with
| QsTypeKind.ArrayType _ -> invoke (buildId s <|?.|> (ident "Copy")) ``(`` [] ``)``
| _ -> buildExpression ex
| _ -> buildExpression ex
and buildNamedItem ex acc =
match acc with
| LocalVariable name ->
let name' =
match ex.ResolvedType.Resolution with
| UserDefinedType udt ->
name |> userDefinedName (Some { Namespace = udt.Namespace; Name = udt.Name })
| _ -> name
buildExpression ex <|.|> ident name'
| _ ->
// TODO: Diagnostics
failwith "Invalid identifier for named item"
and buildAddExpr (exType: ResolvedType) lhs rhs =
match exType.Resolution |> QArrayType with
| Some arrType -> arrType <.> (ident "Add", [ buildExpression lhs; buildExpression rhs ])
| _ -> ``((`` ((buildExpression lhs) <+> (buildExpression rhs)) ``))``
and buildInterpolatedString (s: string) (exs: ImmutableArray<TypedExpression>) =
if exs.Length <> 0 then
let exprs = exs |> Seq.map buildExpression |> Seq.toList
invoke (ident "String.Format") ``(`` (literal s :: exprs) ``)``
else
literal s
and buildId id : ExpressionSyntax =
match id with
| LocalVariable n -> n |> ident :> ExpressionSyntax
| GlobalCallable n -> getOpName context n |> ident :> ExpressionSyntax
| InvalidIdentifier ->
// TODO: Diagnostics
failwith "Received InvalidIdentifier"
and buildCopyAndUpdateExpression (lhsEx: TypedExpression, accEx: TypedExpression, rhsEx) =
match lhsEx.ResolvedType.Resolution |> QArrayType with
| Some arrayType ->
let lhsAsQArray = ``new`` arrayType ``(`` [ buildExpression lhsEx ] ``)``
lhsAsQArray <.> (ident "Modify", [ buildExpression accEx; captureExpression rhsEx ]) // in-place modification
| _ ->
lhsEx.ResolvedType.Resolution
|> function
| UserDefinedType udt ->
let name = QsQualifiedName.New(udt.Namespace, udt.Name)
let decl = findUdt context name
let isUserDefinedType =
function
| UserDefinedType _ -> true
| _ -> false
let getItemName =
function
| Identifier (LocalVariable id, Null) -> id
// TODO: Diagnostics
| _ ->
failwith
"item access expression in copy-and-update expression for user defined type is not a suitable identifier"
let updatedItems = new Dictionary<string, ExpressionSyntax>()
let rec aggregate (lhs: TypedExpression) =
match lhs.Expression with
| CopyAndUpdate (l, i, r) when l.ResolvedType.Resolution |> isUserDefinedType ->
let lhs = aggregate l // need to recur first, or make sure key is not already in dictionary
updatedItems.[getItemName i.Expression] <- captureExpression r
lhs
| _ -> lhs
let lhs = aggregate lhsEx |> buildExpression
updatedItems.[getItemName accEx.Expression] <- captureExpression rhsEx // needs to be after aggregate
let root = lhs <|.|> (ident "Data")
let items = getAllItems root decl.Type
let rec buildArg =
function
| QsTuple args -> args |> Seq.map buildArg |> Seq.toList |> tuple
| QsTupleItem (Named item) ->
updatedItems.TryGetValue item.VariableName
|> function
| true, rhs ->
items.Dequeue() |> ignore
rhs
| _ -> items.Dequeue()
| QsTupleItem _ -> items.Dequeue()
``new`` (``type`` [ justTheName context name ]) ``(`` [ buildArg decl.TypeItems ] ``)``
| _ ->
failwith
"copy-and-update expressions are currently only supported for arrays and user defined types"
and buildTuple many : ExpressionSyntax =
many |> Seq.map captureExpression |> Seq.toList |> tuple // captured since we rely on the native C# tuples
and buildPartial (partialType: ResolvedType) typeParamResolutions opEx args =
let (pIn, pOut) = inAndOutputType partialType // The type of the operation constructed by partial application
let (oIn, _) = inAndOutputType opEx.ResolvedType // The type of the operation accepting the partial tuples.
let buildPartialMapper () = // may only be executed if there are no more type parameters to be resolved
let argName = nextArgName ()
let items = getAllItems (ident argName) pIn
let rec argMapping (expr: TypedExpression) =
let rec buildMissing =
function
| Tuple ts -> ts |> Seq.toList |> List.map buildMissing |> tuple
| _ -> items.Dequeue()
match expr with
| Missing -> buildMissing expr.ResolvedType
| Tuple vt ->
match expr.ResolvedType with
| Tuple ts when ts.Length = vt.Length ->
vt
|> Seq.zip ts
|> Seq.toList
|> List.map (fun (t, v) -> argMapping { v with ResolvedType = t })
|> tuple
// TODO: Diagnostics.
| _ -> failwith "invalid input to code gen in partial application"
| Item ex -> captureExpression ex
// TODO: Diagnostics.
| _ -> failwith "partial application contains an error expression"
let resolvedOrigInputT = ResolvedType.ResolveTypeParameters typeParamResolutions oIn
let mapper =
[
``() =>`` [ argName ] (argMapping { args with ResolvedType = resolvedOrigInputT })
]
``new``
(generic
"Func"
``<<``
[ (roslynTypeName context pIn); (roslynTypeName context resolvedOrigInputT) ]
``>>``)
``(``
mapper
``)``
// Checks if the expression still has type parameters.
// If it does, we can't create the PartialMapper at compile time
// so we just build a partial-tuple and let it be resolved at runtime.
let op = buildExpression opEx
let values = if hasTypeParameters [ pIn; pOut ] then captureExpression args else buildPartialMapper ()
op <.> (ident "Partial", [ values ])
and buildNewUdt n args =
``new`` (``type`` [ justTheName context n ]) ``(`` [ args |> captureExpression ] ``)``
and buildApply returnType op args =
// Checks if the expression points to a non-generic user-defined callable.
// Because these have fully-resolved types in the runtime,
// they don't need to have the return type explicitly in the apply.
let isNonGenericCallable () =
match op.Expression with
| Identifier (_, Value tArgs) when tArgs.Length > 0 -> false
| Identifier (id, _) ->
match id with
| GlobalCallable n ->
let sameName =
match context.current with
| None -> false
| Some name -> n = name
if sameName then // when called recursively, we always need to specify the return type.
false
else
not (hasTypeParameters [ op.ResolvedType ])
| _ -> false
| _ -> false
let useReturnType =
match returnType.Resolution with
| QsTypeKind.UnitType -> false
| _ -> not (isNonGenericCallable ())
let apply =
if useReturnType then
(ident (sprintf "Apply<%s>" (roslynTypeName context returnType)))
else
(ident "Apply")
buildExpression op <.> (apply, [ args |> captureExpression ]) // we need to capture to guarantee that the result accurately reflects any indirect binding of arguments
and buildConditional c t f =
let cond = c |> buildExpression
let whenTrue = t |> captureExpression
let whenFalse = f |> captureExpression
``?`` cond (whenTrue, whenFalse)
and buildRange lhs rEnd =
let args =
lhs.Expression
|> function
| RangeLiteral (start, step) ->
[ (buildExpression start); (buildExpression step); (buildExpression rEnd) ]
| _ -> [ (buildExpression lhs); (buildExpression rEnd) ]
``new`` (``type`` [ "QRange" ]) ``(`` args ``)``
and buildValueArray at elems =
match at.Resolution |> QArrayType with
| Some arrayType -> ``new`` arrayType ``(`` (elems |> Seq.map captureExpression |> Seq.toList) ``)``
// TODO: diagnostics.
| _ -> failwith ""
and buildSizedArray value size =
let valueName = nextArgName ()
var valueName (``:=`` (buildExpression value)) |> ``#line hidden`` |> addStatement
let valueId = { value with Expression = Identifier(LocalVariable valueName, Null); Range = Null }
let supplier = ``() =>`` [] (captureExpression valueId) :> ExpressionSyntax
ident "QArray" <.> (ident "Filled", [ supplier; buildExpression size ])
and buildNewArray b count =
let arrayType = (ArrayType b |> QArrayType).Value
arrayType <.> (ident "Create", [ count |> buildExpression ])
and buildArrayItem a i =
match i.ResolvedType.Resolution with
| Range -> invoke ((buildExpression a) <|.|> (ident "Slice")) ``(`` [ (buildExpression i) ] ``)``
| _ -> item (buildExpression a) [ (buildExpression i) ]
let buildBlock (block: QsScope) =
let builder = new SyntaxBuilder(context)
builder.StartLine <- parent.StartLine
builder.Statements.OnScope block |> ignore
builder.BuiltStatements
let buildSymbolTuple buildTuple buildSymbol symbol =
let rec buildOne =
function
// TODO: Diagnostics
| InvalidItem -> failwith ("InvalidItem received")
| VariableName one -> one |> buildSymbol
| VariableNameTuple many -> many |> Seq.map buildOne |> Seq.toList |> buildTuple
| DiscardedItem -> "_" |> buildSymbol
// While _ inside C# tuple destructs will properly discard the assignment,
// _ can also be used as variable name in C# where a repeated usage will lead to a compilation error.
// We hence auto-generate a name for discarded Q# bindings.
match symbol with
| DiscardedItem -> nextArgName () |> buildSymbol
| _ -> buildOne symbol
let buildSymbolNames buildName =
buildSymbolTuple (String.concat "," >> sprintf "(%s)") buildName
/// returns true if a value of this type contains any arrays
/// -> in particular, this does not include the in- and output type of callables
let rec containsArrays (t: ResolvedType) =
match t.Resolution with
| TupleType ts -> ts |> Seq.exists containsArrays
| ArrayType _ -> true
| _ -> false // no need to check types within callables
/// returns true if the given expression initializes a new QArray instance
let rec isArrayInit ex =
match ex.Expression with
| CopyAndUpdate _
| NewArray _
| ADD _
| ValueArray _ -> true
| CONDITIONAL (_, l, r) -> isArrayInit l && isArrayInit r
| _ -> false
override _.OnExpressionStatement(node: TypedExpression) =
buildExpression node |> statement |> addStatement
QsExpressionStatement node
override _.OnReturnStatement(node: TypedExpression) =
buildExpression node |> Some |> ``return`` |> addStatement
QsReturnStatement node
override _.OnVariableDeclaration(node: QsBinding<TypedExpression>) =
let bindsArrays = node.Rhs.ResolvedType |> containsArrays
let rhs = node.Rhs |> captureExpression
let buildBinding buildName =
let lhs = node.Lhs |> buildSymbolNames buildName
if bindsArrays then // we need to cast to the correct type here (in particular to IQArray for arrays)
let t = roslynTypeName context node.Rhs.ResolvedType
var lhs (``:=`` <| cast t rhs) |> addStatement
else
var lhs (``:=`` <| rhs) |> addStatement
match node.Kind with
| MutableBinding ->
match node.Lhs with
// no need to insert a destructing statement first
| VariableName varName ->
match node.Rhs.ResolvedType.Resolution |> QArrayType with
| Some _ when isArrayInit node.Rhs -> // avoid unnecessary copies on construction
var varName (``:=`` <| rhs) |> addStatement
| Some arrType -> // we need to make sure to bind to a new QArray instance here
let qArray = ``new`` arrType ``(`` [ rhs ] ``)``
var varName (``:=`` <| qArray) |> addStatement
| _ -> buildBinding id
// we first need to destruct here, and then make sure all QArrays are built
| VariableNameTuple _ when bindsArrays ->
// insert a destructing statement
let prefix = nextArgName ()
let imName = sprintf "%s%s__" prefix
buildBinding imName
// build the actual binding, making sure all necessary QArrays instances are created
for localVar in parent.DeclarationsInStatement.Variables do
let varName = localVar.VariableName
match localVar.Type.Resolution |> QArrayType with
| Some arrType ->
let qArray = ``new`` arrType ``(`` [ ident (imName varName) ] ``)``
var varName (``:=`` <| qArray) |> addStatement
| _ -> var varName (``:=`` <| ident (imName varName)) |> addStatement
| _ -> buildBinding id
| _ -> buildBinding id
QsVariableDeclaration node
override _.OnValueUpdate(node: QsValueUpdate) =
let rec varNames onTuple onItem (ex: TypedExpression) =
match ex.Expression with
| MissingExpr -> onItem "_"
| Identifier (LocalVariable id, Null) -> onItem id
| ValueTuple vs -> vs |> Seq.map (varNames onTuple onItem) |> onTuple
// TODO: diagnostics.
| _ -> failwith "unexpected expression in lhs of value update"
let lhs, rhs = buildExpression node.Lhs, captureExpression node.Rhs
match node.Lhs.Expression with
| MissingExpr -> var (nextArgName ()) (``:=`` <| buildExpression node.Rhs) |> addStatement
// no need to insert a destructing statement first
| Identifier (LocalVariable id, Null) ->
let matchesIdentifier (ex: TypedExpression) =
match ex.Expression with
| Identifier (LocalVariable rhsId, Null) when rhsId = id -> true
| _ -> false
let isArray =
function
| ArrayType _ -> true
| _ -> false
match node.Rhs.Expression with
| CopyAndUpdate (l, a, r) when l |> matchesIdentifier && l.ResolvedType.Resolution |> isArray -> // we do an in-place modification in this case
let access, rhs = buildExpression a, captureExpression r
(buildExpression l) <.> (ident "Modify", [ access; rhs ]) |> statement |> addStatement
| _ when node.Rhs |> matchesIdentifier -> () // unnecessary statement
| _ ->
node.Rhs.ResolvedType.Resolution
|> QArrayType
|> function
| Some _ when isArrayInit node.Rhs -> // avoid unnecessary copies here
lhs <-- rhs |> statement |> addStatement
| Some arrType -> // we need to make sure to bind to a new QArray instance here
let qArray = ``new`` arrType ``(`` [ rhs ] ``)``
lhs <-- qArray |> statement |> addStatement
| _ -> lhs <-- rhs |> statement |> addStatement
// we first need to destruct here, and then make sure all QArrays are built
| _ when containsArrays node.Rhs.ResolvedType ->
// insert a destructing statement
let prefix = nextArgName ()
let imName name =
if name = "_" then name else sprintf "%s%s__" prefix name
let tempBinding = varNames (fun ids -> String.Join(",", ids) |> sprintf "(%s)") imName node.Lhs
var tempBinding (``:=`` <| rhs) |> addStatement
// build the actual binding, making sure all necessary QArrays instances are created
let ids = varNames (Seq.collect id) (fun id -> seq { if id <> "_" then yield id }) node.Lhs
for id in ids do
let decl = parent.DeclarationsInScope.Variables |> Seq.tryFind (fun d -> d.VariableName = id)
match decl |> Option.map (fun d -> d.Type.Resolution |> QArrayType) |> Option.flatten with
| Some arrType -> // we need to make sure to create a new QArray instance here
let qArray = ``new`` arrType ``(`` [ imName id |> ident ] ``)``
(ident id) <-- qArray |> statement |> addStatement
| _ -> (ident id) <-- (imName id |> ident) |> statement |> addStatement
| _ -> lhs <-- rhs |> statement |> addStatement
QsValueUpdate node
override _.OnConditionalStatement(node: QsConditionalStatement) =
let all = node.ConditionalBlocks
let (cond, thenBlock) = all.[0]
let cond = cond |> buildExpression
let thenBlock = thenBlock.Body |> buildBlock
let others =
[
for i in 1 .. all.Length - 1 ->
let (cond, block) = all.[i]
cond |> buildExpression, block.Body |> buildBlock
]
let elseBlock =
match node.Default with
| Null -> None
| Value block -> ``else`` (buildBlock block.Body) |> Some
``if`` ``(`` cond ``)`` thenBlock (``elif`` others elseBlock) |> addStatement
QsConditionalStatement node
override _.OnForStatement(node: QsForStatement) =
let sym = node.LoopItem |> fst |> buildSymbolNames id
let range = node.IterationValues |> captureExpression
let body = node.Body |> buildBlock
foreach ``(`` sym ``in`` range ``)`` body |> addStatement
QsForStatement node
override _.OnWhileStatement(node: QsWhileStatement) =
let cond = node.Condition |> buildExpression
let body = node.Body |> buildBlock
``while`` ``(`` cond ``)`` body |> addStatement
QsWhileStatement node
override _.OnRepeatStatement rs =
let buildTest test fixup =
let condition = buildExpression test
let thens = [ break ]
let elses = buildBlock fixup
``if`` ``(`` condition ``)`` thens (Some(``else`` elses))
``while``
``(``
``true``
``)``
((buildBlock rs.RepeatBlock.Body) @ [ buildTest rs.SuccessCondition rs.FixupBlock.Body ])
|> addStatement
QsRepeatStatement rs
override _.OnQubitScope(using: QsQubitScope) =
let (alloc, release) =
match using.Kind with
| Allocate -> "Allocate__", "Release__"
| Borrow -> "Borrow__", "Return__"
let rec removeDiscarded sym =
match sym with
| VariableName _ -> sym
| DiscardedItem -> nextArgName () |> VariableName
| VariableNameTuple many ->
many |> Seq.map removeDiscarded |> ImmutableArray.CreateRange |> VariableNameTuple
| InvalidItem -> failwith ("InvalidItem received")
let rec buildInitializeExpression (exp: ResolvedInitializer) =
match exp.Resolution with
| SingleQubitAllocation -> ((ident alloc) <.> (ident "Apply", []))
| QubitRegisterAllocation e -> ((ident alloc) <.> (ident "Apply", [ (buildExpression e) ]))
| QubitTupleAllocation many -> many |> Seq.map buildInitializeExpression |> List.ofSeq |> tuple
// todo: diagnostics
| InvalidInitializer -> failwith ("InvalidInitializer received")
let rec buildReleaseExpression (symbol, expr: ResolvedInitializer) : StatementSyntax list =
let currentLine = parent.LineNumber
parent.LineNumber <- Some 0
let buildOne sym =
(ident release) <.> (ident "Apply", [ (ident (sym)) ]) |> (statement >> withLineNumber)
let rec buildDeconstruct sym (rhs: ResolvedInitializer) =
match rhs.Resolution with
| SingleQubitAllocation -> [ buildOne sym ]
| QubitRegisterAllocation _ -> [ buildOne sym ]
| QubitTupleAllocation aa ->
aa
|> Seq.mapi (fun i e -> buildDeconstruct (sprintf "%s.Item%d" sym (i + 1)) e)
|> Seq.toList
|> List.concat
| InvalidInitializer -> failwith ("InvalidInitializer received")
let releases =
match (symbol, expr.Resolution) with
| VariableName one, SingleQubitAllocation -> [ buildOne one ]
| VariableName one, QubitRegisterAllocation _ -> [ buildOne one ]
| VariableName one, QubitTupleAllocation _ -> (buildDeconstruct one expr)
| VariableNameTuple ss, QubitTupleAllocation aa ->
Seq.zip ss aa |> Seq.map buildReleaseExpression |> Seq.toList |> List.concat
| _ -> failwith ("InvalidItem received")
parent.LineNumber <- currentLine
releases
let symbols = removeDiscarded using.Binding.Lhs
let deallocationFlagName = nextArgName ()
let deallocationFlagIdentifier = ident deallocationFlagName
// allocations and deallocations
let lhs = symbols |> buildSymbolNames id
let rhs = using.Binding.Rhs |> buildInitializeExpression
let allocation = var lhs (``:=`` <| rhs) |> withLineNumber
let deallocation = buildReleaseExpression (symbols, using.Binding.Rhs)
// To force that exceptions thrown during the execution of the allocation scope take precedence over the ones thrown upon release
// we catch all exceptions in a variable and throw after releaseing if necessary.
// Indicates if deallocation is needed. It is not needed when exception is thrown.
let deallocationFlagDeclaration =
``typed var`` "bool" deallocationFlagName (``:=`` ``true`` |> Some) |> ``#line hidden``
:> StatementSyntax
let catch =
let setFlagToFalse = deallocationFlagIdentifier <-- ``false`` |> statement
catch None [ setFlagToFalse; throw None ] // use standard mechanism to rethrow the exception by using "throw;"
let finallyBlock = [ ``if`` ``(`` deallocationFlagIdentifier ``)`` deallocation None ]
let body =
``try``
(buildBlock using.Body)
[ catch |> ``#line hidden`` ]
(``finally`` finallyBlock |> ``#line hidden`` |> Some)
let statements = [ allocation; deallocationFlagDeclaration; body ]
// Put all statements into their own brackets so variable names have their own context.
// Make sure the brackets get #line hidden:
let currentLine = parent.LineNumber
parent.LineNumber <- parent.LineNumber |> Option.map (fun _ -> 0)
``{{`` statements ``}}`` |> addStatement
parent.LineNumber <- currentLine
QsQubitScope using
override _.OnFailStatement fs =
let failException = ``new`` (``type`` [ "ExecutionFailException" ]) ``(`` [ (buildExpression fs) ] ``)``
addStatement (throw <| Some failException)
QsFailStatement fs
and NamespaceBuilder(parent: SyntaxBuilder) =
inherit NamespaceTransformation(parent, TransformationOptions.NoRebuild)