Subrs.Structures.cs 19.2 KB
Newer Older
1
/* Copyright 2010-2018 Jesse McGrew
Jesse McGrew's avatar
Jesse McGrew committed
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 * 
 * This file is part of ZILF.
 * 
 * ZILF is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * ZILF is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with ZILF.  If not, see <http://www.gnu.org/licenses/>.
 */
Jesse McGrew's avatar
Jesse McGrew committed
18

Jesse McGrew's avatar
Jesse McGrew committed
19
using System;
Jesse McGrew's avatar
Jesse McGrew committed
20
using System.Collections.Generic;
21
using System.Diagnostics;
22
using System.Linq;
23
using System.Runtime.Serialization;
24
25
using Zilf.Interpreter.Values;
using Zilf.Language;
26
using Zilf.Diagnostics;
27
using Zilf.Common;
28
using JetBrains.Annotations;
29
30
31
32

namespace Zilf.Interpreter
{
    static partial class Subrs
33
34
    {
        [NotNull]
35
        [Subr("EMPTY?")]
36
        public static ZilObject EMPTY_P([NotNull] Context ctx, [NotNull] IStructure st)
37
        {
38
            return st.IsEmpty ? ctx.TRUE : ctx.FALSE;
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
        }

        /*[Subr]
        public static ZilObject FIRST(Context ctx, ZilObject[] args)
        {
            if (args.Length != 1)
                throw new InterpreterError("FIRST", 1, 1);

            IStructure st = args[0] as IStructure;
            if (st == null)
                throw new InterpreterError("FIRST: arg must be a structure");

            return st.GetFirst();
        }*/

54
55
        /// <exception cref="InterpreterError"><paramref name="st"/> has fewer than <paramref name="skip"/> elements.</exception>
        [NotNull]
56
        [Subr]
57
        public static ZilObject REST(Context ctx, [NotNull] IStructure st, int skip = 1)
58
59
60
        {
            var result = (ZilObject)st.GetRest(skip);
            if (result == null)
61
                throw new InterpreterError(InterpreterMessages._0_Not_Enough_Elements, "REST");
62
            return result.GetPrimitive(ctx);
63
64
        }

65
66
        /// <exception cref="InterpreterError">The type of <paramref name="st"/> does not support this operation, or <paramref name="st"/> has not been RESTed at least <paramref name="skip"/> elements.</exception>
        [NotNull]
Jesse McGrew's avatar
Jesse McGrew committed
67
        [Subr]
68
        public static ZilObject BACK(Context ctx, [NotNull] IStructure st, int skip = 1)
Jesse McGrew's avatar
Jesse McGrew committed
69
70
71
72
73
        {
            try
            {
                var result = (ZilObject)st.GetBack(skip);
                if (result == null)
74
                    throw new InterpreterError(InterpreterMessages._0_Not_Enough_Elements);
Jesse McGrew's avatar
Jesse McGrew committed
75
76
                return result;
            }
77
            catch (NotSupportedException)
Jesse McGrew's avatar
Jesse McGrew committed
78
            {
79
                throw new InterpreterError(InterpreterMessages._0_Not_Supported_By_Type, "BACK");
Jesse McGrew's avatar
Jesse McGrew committed
80
81
82
            }
        }

83
84
        /// <exception cref="InterpreterError">The type of <paramref name="st"/> does not support this operation.</exception>
        [NotNull]
Jesse McGrew's avatar
Jesse McGrew committed
85
        [Subr]
86
        public static ZilObject TOP(Context ctx, [NotNull] IStructure st)
Jesse McGrew's avatar
Jesse McGrew committed
87
88
89
90
91
        {
            try
            {
                return (ZilObject)st.GetTop();
            }
92
            catch (NotSupportedException)
Jesse McGrew's avatar
Jesse McGrew committed
93
            {
94
                throw new InterpreterError(InterpreterMessages._0_Not_Supported_By_Type, "TOP");
Jesse McGrew's avatar
Jesse McGrew committed
95
96
97
            }
        }

98
99
        /// <exception cref="InterpreterError"><paramref name="beginning"/> or <paramref name="end"/> are negative, or the type of <paramref name="st"/> does not support this operation.</exception>
        [NotNull]
Jesse McGrew's avatar
Jesse McGrew committed
100
        [Subr]
101
        public static ZilObject GROW(Context ctx, [NotNull] IStructure st, int end, int beginning)
Jesse McGrew's avatar
Jesse McGrew committed
102
103
104
        {
            if (end < 0 || beginning < 0)
            {
105
                throw new InterpreterError(InterpreterMessages._0_Sizes_Must_Be_Nonnegative, "GROW");
Jesse McGrew's avatar
Jesse McGrew committed
106
107
108
109
110
111
112
113
114
115
116
            }

            try
            {
                if (end > 0 || beginning > 0)
                {
                    st.Grow(end, beginning, ctx.FALSE);
                }

                return (ZilObject)st.GetTop();
            }
117
            catch (NotSupportedException)
Jesse McGrew's avatar
Jesse McGrew committed
118
            {
119
                throw new InterpreterError(InterpreterMessages._0_Not_Supported_By_Type, "GROW");
Jesse McGrew's avatar
Jesse McGrew committed
120
121
122
            }
        }

123
124
        /// <exception cref="InterpreterError"><paramref name="idx"/> is past the end of <paramref name="st"/>.</exception>
        [NotNull]
125
        [Subr]
126
        public static ZilObject NTH(Context ctx, [NotNull] IStructure st, int idx)
127
        {
Jesse McGrew's avatar
Jesse McGrew committed
128
            var result = st[idx - 1];
129
            if (result == null)
130
                throw new InterpreterError(InterpreterMessages._0_Reading_Past_End_Of_Structure, "NTH");
131
132
133
134

            return result;
        }

135
136
        /// <exception cref="InterpreterError"><paramref name="idx"/> is past the end of <paramref name="st"/>, or <paramref name="st"/> is read-only.</exception>
        [NotNull]
137
        [Subr]
138
        public static ZilObject PUT(Context ctx, [NotNull] IStructure st, int idx, ZilObject newValue)
139
        {
140
141
142
143
            try
            {
                st[idx - 1] = newValue;
            }
144
            catch (ArgumentOutOfRangeException)
145
            {
146
147
148
149
150
                throw new InterpreterError(InterpreterMessages._0_Writing_Past_End_Of_Structure, "PUT");
            }
            catch (NotSupportedException)
            {
                throw new InterpreterError(InterpreterMessages._0_Element_1_Is_Read_Only, "PUT", idx);
151
152
            }

153
            return (ZilObject)st;
154
155
        }

156
        [NotNull]
157
        [Subr]
158
        public static ZilObject OFFSET(Context ctx, int offset, [NotNull] ZilObject structurePattern, [CanBeNull] ZilObject valuePattern = null)
159
160
161
162
        {
            return new ZilOffset(offset, structurePattern, valuePattern ?? ctx.GetStdAtom(StdAtom.ANY));
        }

163
        [NotNull]
164
        [Subr]
165
        public static ZilObject INDEX(Context ctx, [NotNull] ZilOffset offset)
166
167
168
169
        {
            return new ZilFix(offset.Index);
        }

170
        [NotNull]
171
        [Subr]
172
        public static ZilObject LENGTH(Context ctx, [NotNull] IStructure st)
173
174
175
176
        {
            return new ZilFix(st.GetLength());
        }

177
        [NotNull]
178
        [Subr("LENGTH?")]
179
        public static ZilObject LENGTH_P(Context ctx, [NotNull] IStructure st, int limit)
180
        {
181
            var length = st.GetLength(limit);
182
            return length != null ? new ZilFix((int)length) : ctx.FALSE;
183
184
        }

185
186
        /// <exception cref="InterpreterError"><paramref name="list"/> is empty.</exception>
        [NotNull]
187
        [Subr]
188
        public static ZilObject PUTREST(Context ctx, [NotNull] ZilListoidBase list, [NotNull] ZilListoidBase newRest)
189
        {
190
191
192
            if (list.IsEmpty)
                throw new InterpreterError(InterpreterMessages._0_Writing_Past_End_Of_Structure, "PUTREST");

193
194
195
196
            if (newRest is ZilList newRestList)
            {
                list.Rest = newRestList;
            }
197
            else
198
            {
199
                list.Rest = new ZilList(newRest);
200
            }
201
202
203
204

            return list;
        }

205
206
        /// <exception cref="InterpreterError"><paramref name="amount"/> is negative, or <paramref name="from"/> or <paramref name="dest"/> are too short, or the types of <paramref name="from"/> and <paramref name="dest"/> are incompatible.</exception>
        [NotNull]
207
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1800:DoNotCastUnnecessarily")]
208
        [Subr]
209
210
        public static ZilObject SUBSTRUC(Context ctx, [NotNull] IStructure from, int rest = 0, int? amount = null,
            [CanBeNull] IStructure dest = null)
211
        {
212
            if (amount != null)
213
            {
214
                var max = from.GetLength(rest + (int)amount);
215
                if (max != null && max.Value - rest < amount)
216
217
218
219
220
                    throw new InterpreterError(
                        InterpreterMessages._0_1_Element1s_Requested_But_Only_2_Available,
                        "SUBSTRUC",
                        amount,
                        max.Value - rest);
221
222
223
224
225
226
227
            }
            else
            {
                amount = from.GetLength() - rest;
            }

            if (amount < 0)
228
                throw new InterpreterError(InterpreterMessages._0_Negative_Element_Count, "SUBSTRUC");
229

230
231
            var fromObj = (ZilObject)from;
            var destObj = (ZilObject)dest;
232
            var primitive = (IStructure)fromObj.GetPrimitive(ctx);
233

234
            if (destObj != null)
235
            {
236
                // modify an existing structure
237
                if (destObj.PrimType != fromObj.PrimType)
238
                    throw new InterpreterError(InterpreterMessages._0_Destination_Must_Have_Same_Primtype_As_Source, "SUBSTRUC");
239
240
241

                int i;

242
                switch (dest)
243
                {
244
                    case ZilListoidBase list:
245
                        foreach (var item in primitive.Skip(rest).Take((int)amount))
246
247
                        {
                            if (list.IsEmpty)
248
                                throw new InterpreterError(InterpreterMessages._0_Destination_Too_Short, "SUBSTRUC");
249

250
251
                            Debug.Assert(list.Rest != null);

252
253
254
255
256
                            list.First = item;
                            list = list.Rest;
                        }
                        break;

257
                    case ZilString str:
258
                        // this is crazy inefficient, but works with ZilString and OffsetString
259
                        // TODO: method on ZilString to do this more efficiently?
260
                        for (i = 0; i < amount; i++)
261
                            str[i] = primitive[i + rest];
262
263
                        break;

264
                    case ZilVector vector:
265
                        i = 0;
266
                        foreach (var item in primitive.Skip(rest).Take((int)amount))
267
268
                        {
                            if (i >= vector.GetLength())
269
                                throw new InterpreterError(InterpreterMessages._0_Destination_Too_Short, "SUBSTRUC");
270
271
272
273
274
275

                            vector[i++] = item;
                        }
                        break;

                    default:
276
                        throw new InterpreterError(InterpreterMessages._0_Destination_Type_Not_Supported_1, "SUBSTRUC", destObj.GetTypeAtom(ctx));
277
278
                }

279
                return destObj;
280
            }
281
282

            // no destination, return a new structure
283
            switch (fromObj.PrimType)
284
            {
285
                case PrimType.LIST:
286
                    return new ZilList(primitive.Skip(rest).Take((int)amount));
287

288
289
                case PrimType.STRING:
                    return ZilString.FromString(((ZilString)primitive).Text.Substring(rest, (int)amount));
290

291
292
                case PrimType.TABLE:
                    throw new InterpreterError(InterpreterMessages._0_Primtype_TABLE_Not_Supported, "SUBSTRUC");
293

294
295
                case PrimType.VECTOR:
                    return new ZilVector(((ZilVector)primitive).Skip(rest).Take((int)amount).ToArray());
296

297
                default:
298
                    throw UnhandledCaseException.FromEnum(fromObj.PrimType, "structured primtype");
299
300
301
            }
        }

302
        [NotNull]
303
        [Subr]
304
        public static ZilObject MEMBER(Context ctx, [NotNull] ZilObject needle, [NotNull] IStructure haystack)
305
        {
306
307
308
309
310
311
312
313
314
315
316
317
318
319
            if (needle.PrimType == PrimType.STRING && ((ZilObject)haystack).PrimType == PrimType.STRING)
            {
                string n = ((ZilString)needle.GetPrimitive(ctx)).Text;
                if (n != "")
                {
                    string h = ((ZilString)((ZilObject)haystack).GetPrimitive(ctx)).Text;
                    int pos = h.IndexOf(n, StringComparison.Ordinal);
                    if (pos >= 0)
                    {
                        return (ZilObject)haystack.GetRest(pos) ?? ctx.FALSE;
                    }
                }
            }

320
            return PerformMember(ctx, needle, haystack, (a, b) => a.StructurallyEquals(b));
321
322
        }

323
        [NotNull]
324
        [Subr]
325
        public static ZilObject MEMQ(Context ctx, [NotNull] ZilObject needle, [NotNull] IStructure haystack)
326
        {
327
            return PerformMember(ctx, needle, haystack, (a, b) => a.ExactlyEquals(b));
328
329
        }

330
331
332
        [NotNull]
        static ZilObject PerformMember(Context ctx, [NotNull] ZilObject needle, [NotNull] IStructure haystack,
            [NotNull] Func<ZilObject, ZilObject, bool> equality)
333
        {
334
            while (haystack != null && !haystack.IsEmpty)
335
336
337
338
339
340
341
342
343
344
            {
                if (equality(needle, haystack.GetFirst()))
                    return (ZilObject)haystack;

                haystack = haystack.GetRest(1);
            }

            return ctx.FALSE;
        }

345
#pragma warning disable CS0649
Jesse McGrew's avatar
Jesse McGrew committed
346
347
348
349
350
351
352
        [ZilSequenceParam]
        public struct AdditionalSortParam
        {
            public ZilVector Vector;
            [ZilOptional(Default = 1)]
            public int RecordSize;
        }
353
#pragma warning restore CS0649
Jesse McGrew's avatar
Jesse McGrew committed
354

355
356
357
358
359
360
361
362
363
364
365
        [Serializable]
        class SortAbortedException : Exception
        {
            public ZilResult ZilResult { get; }

            public SortAbortedException(ZilResult zilResult)
            {
                ZilResult = zilResult;
            }

            protected SortAbortedException(
366
                [NotNull] SerializationInfo info,
367
368
369
370
371
                StreamingContext context) : base(info, context)
            {
            }
        }

Jesse McGrew's avatar
Jesse McGrew committed
372
        [Subr]
373
        public static ZilResult SORT(Context ctx,
374
375
376
            [NotNull] [Decl("<OR FALSE APPLICABLE>")] ZilObject predicate,
            [NotNull] ZilVector vector, int recordSize = 1, int keyOffset = 0,
            [CanBeNull] AdditionalSortParam[] additionalSorts = null)
Jesse McGrew's avatar
Jesse McGrew committed
377
378
        {
            if (keyOffset < 0 || keyOffset >= recordSize)
Jesse McGrew's avatar
Jesse McGrew committed
379
                throw new InterpreterError(InterpreterMessages._0_Expected_0__Key_Offset__Record_Size, "SORT");
Jesse McGrew's avatar
Jesse McGrew committed
380
381

            var vectorLength = vector.GetLength();
Jesse McGrew's avatar
Jesse McGrew committed
382
            int numRecords = Math.DivRem(vectorLength, recordSize, out var remainder);
Jesse McGrew's avatar
Jesse McGrew committed
383
384

            if (remainder != 0)
Jesse McGrew's avatar
Jesse McGrew committed
385
                throw new InterpreterError(InterpreterMessages._0_Vector_Length_Must_Be_A_Multiple_Of_Record_Size, "SORT");
Jesse McGrew's avatar
Jesse McGrew committed
386
387
388
389
390
391

            if (additionalSorts != null)
            {
                foreach (var asp in additionalSorts)
                {
                    if (asp.RecordSize < 1)
Jesse McGrew's avatar
Jesse McGrew committed
392
                        throw new InterpreterError(InterpreterMessages._0_Expected_0__Key_Offset__Record_Size, "SORT");
Jesse McGrew's avatar
Jesse McGrew committed
393
394

                    var len = asp.Vector.GetLength();
Jesse McGrew's avatar
Jesse McGrew committed
395
                    int recs = Math.DivRem(len, asp.RecordSize, out var rem);
Jesse McGrew's avatar
Jesse McGrew committed
396
397

                    if (rem != 0)
Jesse McGrew's avatar
Jesse McGrew committed
398
                        throw new InterpreterError(InterpreterMessages._0_Vector_Length_Must_Be_A_Multiple_Of_Record_Size, "SORT");
Jesse McGrew's avatar
Jesse McGrew committed
399
400

                    if (recs != numRecords)
Jesse McGrew's avatar
Jesse McGrew committed
401
                        throw new InterpreterError(InterpreterMessages._0_All_Vectors_Must_Have_The_Same_Number_Of_Records, "SORT");
Jesse McGrew's avatar
Jesse McGrew committed
402
403
404
                }
            }

405
            ZilObject KeySelector(int i) => vector[i * recordSize + keyOffset];
Jesse McGrew's avatar
Jesse McGrew committed
406
407
408
409
410
411
            Comparison<ZilObject> comparison;

            if (predicate.IsTrue)
            {
                // user-provided comparison
                var applicable = predicate.AsApplicable(ctx);
412
413
                Debug.Assert(applicable != null);

Jesse McGrew's avatar
Jesse McGrew committed
414
415
416
417
418
419
420
                var args = new ZilObject[2];
                comparison = (a, b) =>
                {
                    // greater?
                    args[0] = a;
                    args[1] = b;

421
422
423
424
425
                    var zr = applicable.ApplyNoEval(ctx, args);
                    if (zr.ShouldPass())
                        throw new SortAbortedException(zr);

                    if (((ZilObject)zr).IsTrue)
Jesse McGrew's avatar
Jesse McGrew committed
426
427
428
429
430
431
                        return 1;

                    // less?
                    args[0] = b;
                    args[1] = a;

432
433
434
435
436
                    zr = applicable.ApplyNoEval(ctx, args);
                    if (zr.ShouldPass())
                        throw new SortAbortedException(zr);

                    if (((ZilObject)zr).IsTrue)
Jesse McGrew's avatar
Jesse McGrew committed
437
438
439
440
441
442
443
444
445
446
447
448
449
                        return -1;

                    // equal
                    return 0;
                };
            }
            else
            {
                // default comparison
                comparison = (a, b) =>
                {
                    if (a.GetTypeAtom(ctx) != b.GetTypeAtom(ctx))
                    {
450
                        throw new InterpreterError(InterpreterMessages._0_Keys_Must_Have_The_Same_Type_To_Use_Default_Comparison, "SORT");
Jesse McGrew's avatar
Jesse McGrew committed
451
452
453
454
455
456
457
458
                    }

                    a = a.GetPrimitive(ctx);
                    b = b.GetPrimitive(ctx);

                    switch (a.PrimType)
                    {
                        case PrimType.ATOM:
459
                            return string.Compare(((ZilAtom)a).Text, ((ZilAtom)b).Text, StringComparison.Ordinal);
Jesse McGrew's avatar
Jesse McGrew committed
460
461
462
463
464

                        case PrimType.FIX:
                            return ((ZilFix)a).Value.CompareTo(((ZilFix)b).Value);

                        case PrimType.STRING:
465
                            return string.Compare(((ZilString)a).Text, ((ZilString)b).Text, StringComparison.Ordinal);
Jesse McGrew's avatar
Jesse McGrew committed
466
467

                        default:
468
                            throw new InterpreterError(InterpreterMessages._0_Key_Primtypes_Must_Be_ATOM_FIX_Or_STRING_To_Use_Default_Comparison, "SORT");
Jesse McGrew's avatar
Jesse McGrew committed
469
470
471
472
                    }
                };
            }

473
474
475
476
477
            try
            {
                // sort
                var sortedIndexes =
                    Enumerable.Range(0, numRecords)
478
                        .OrderBy(KeySelector, Comparer<ZilObject>.Create(comparison))
479
                        .ToArray();
Jesse McGrew's avatar
Jesse McGrew committed
480

481
482
                // write output
                RearrangeVector(vector, recordSize, sortedIndexes);
Jesse McGrew's avatar
Jesse McGrew committed
483

484
485
486
487
488
489
490
491
492
493
                if (additionalSorts != null)
                    foreach (var asp in additionalSorts)
                        RearrangeVector(asp.Vector, asp.RecordSize, sortedIndexes);

                return vector;
            }
            catch (SortAbortedException ex)
            {
                return ex.ZilResult;
            }
494
495
496
497
            catch (Exception wrapper) when (wrapper.InnerException is SortAbortedException ex)
            {
                return ex.ZilResult;
            }
Jesse McGrew's avatar
Jesse McGrew committed
498
499
        }

500
        static void RearrangeVector([NotNull] ZilVector vector, int recordSize, [NotNull] int[] desiredIndexOrder)
Jesse McGrew's avatar
Jesse McGrew committed
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
        {
            var output = new List<ZilObject>(vector.GetLength());

            foreach (var srcIndex in desiredIndexOrder)
            {
                for (int i = 0; i < recordSize; i++)
                {
                    output.Add(vector[srcIndex * recordSize + i]);
                }
            }

            for (int i = 0; i < output.Count; i++)
            {
                vector[i] = output[i];
            }
        }
517
518
    }
}