سریال سازی داده های باینری

عملیات MTProto مستلزم آن است که انواع داده های ابتدایی و ترکیبی و همچنین پرس و جوهایی که چنین انواع داده ای به عنوان آرگومان به آنها ارسال می شود یا توسط آنها برگردانده می شوند، در قالب دودویی (به عنوان مثال سریالی) منتقل شوند. زبان TL برای توصیف انواع داده هایی که قرار است سریال شوند استفاده می شود.

تعاریف عمومی

برای اهداف ما، ما می توانیم یک نوع را با مجموعه مقادیر (سریالی) آن که به عنوان رشته ها (دنباله های محدود) اعداد 32 بیتی (به ترتیب انددی ارسال شده) درک می شوند، شناسایی کنیم.

• الفبای (A)، در این مورد، مجموعه ای از اعداد 32 بیتی است (معمولاً با علامت، یعنی بی ن-2^31 و 2^31 - 1).
• مقدار، در این مورد، مانند یک رشته در الفبای A، i است. ه. یک دنباله متناهی (احتمالاً خالی) از اعداد 32 بیتی. مجموعه همه این دنباله ها به عنوان A * تعیین می شود.
• نوع، برای اهداف ما، همان مجموعه مقادیر قانونی یک نوع است، i. ه. برخی از مجموعه های T که زیرمجموعه ای از A* است و یک کد پیشوند است (یعنی هیچ عنصری از T ممکن است پیشوند هیچ عنصر دیگری نباشد). بنابراین، هر دنباله ای از A* نمی تواند حاوی بیش از یک پیشوند باشد که عضوی از T است.
• مقدار نوع T هر دنباله ای (مقدار) است که عضوی از T به عنوان زیر مجموعه A* باشد.
• انواع سازگار، انواع T و T' هستند که به عنوان زیرمجموعه های A* تلاقی نمی کنند، به طوری که اتحاد T و T' یک کد پیشوند است.
• سیستم هماهنگ انواع مجموعه ای متناهی یا نامتناهی از انواع T_1، . T_n، . به طوری که هر دو نوع از این مجموعه سازگار هستند.
• نوع داده به معنای تعریف بالا همان نوع است.
• نوع تابعی نوعی است که یک تابع را توصیف می کند. این یک نوع به معنای تعریف بالا نیست. در ابتدا، وجود انواع تابعی را نادیده می گیریم و فقط انواع داده ها را توصیف می کنیم. با این حال، در واقعیت، انواع تابعی بعداً در برخی از توسعه های این سیستم با استفاده از ترکیب کننده های به اصطلاح موقت پیاده سازی خواهند شد.

ترکیب کننده ها، سازنده ها، انواع داده های مرکب

• Combinator تابعی است که آرگومان هایی از انواع خاصی را می گیرد و مقداری از نوع دیگری را برمی گرداند. ما معمولاً به ترکیب کننده هایی نگاه می کنیم که انواع آرگومان و نتیجه آن ها انواع داده ها (به جای انواع تابعی) هستند.
• Arity (ترکیب) یک عدد صحیح غیر منفی است، تعداد آرگومان های ترکیب کننده.
• شناسه ترکیبی یک شناسه است که با یک حرف رومی کوچک شروع می شود که به طور منحصر به فرد ترکیب کننده را مشخص می کند.
• شماره ترکیبی یا نام ترکیبی یک عدد 32 بیتی است (یعنی عنصر A) که به طور منحصر به فرد یک ترکیب کننده را مشخص می کند. بیشتر اوقات ، این CRC32 از رشته حاوی توضیحات ترکیبی بدون قسمت نهایی نهایی است و با یک فضای بین لکسوم های پیوسته. این همیشه در محدوده 0x01000000 تا 0xffffff00 قرار می گیرد. بالاترین 256 مقادیر برای ترکیبات به اصطلاح تابش موقت که برای انتقال توابع استفاده می شود ، محفوظ است. ما غالباً به عنوان Combinator نام ترکیب کننده با نقل قول های منفرد را نشان می دهیم: "Combinator".
• توضیحات ترکیبی رشته ای از فرمت combinator_name type_arg_1 است. type_arg_n = type_res ؛جایی که n مخفف Arity of the Combinator است ، Type_Arg_i نوع آرگومان I-Th است (یا بهتر بگوییم رشته ای با نام ترکیب کننده) و Type_res نوع مقدار Combinator است.
• سازنده ترکیبی است که نمی تواند محاسبه شود (کاهش می یابد). این برای نشان دادن انواع داده های کامپوزیت استفاده می شود. به عنوان مثال ، ترکیب "int_tree" با توضیحات int_tree inttree inttree = inttree ، در کنار Combinator خالی_tree = inttree ، ممکن است برای تعریف یک نوع داده کامپوزیت به نام "inttree" استفاده شود که مقادیر را به شکل درختان باینری با عدد صحیح به عنوان گره می گیرد.
• عملکرد (ترکیب کاربردی) ترکیبی است که ممکن است به شرط ارائه تعداد لازم از آرگومان های انواع لازم محاسبه شود (کاهش می یابد). نتیجه محاسبه عبارتی است که فقط از سازندگان و مقادیر نوع پایه تشکیل شده است.
• فرم طبیعی عبارتی است که فقط از سازندگان و مقادیر نوع پایه تشکیل شده است. آنچه که معمولاً نتیجه محاسبه یک تابع است.
• شناسه نوع شناسه ای است که به طور معمول با یک حرف بزرگ در اسکریپت رومی شروع می شود و به طور منحصر به فرد نوع را مشخص می کند.
• شماره یا نام نوع یک شماره 32 بیتی است که به طور منحصر به فرد یک نوع را مشخص می کند. این به طور معمول مجموع مقادیر CRC32 از توضیحات سازندگان نوع است.
• توضیحات (کامپوزیت) نوع T مجموعه ای از توضیحات کلیه سازندگان است که مقادیر T نوع را در خود جای می دهند. این به طور معمول به عنوان متن با هر رشته حاوی توضیحات یک سازنده واحد نوشته شده است. در اینجا توضیحی از نوع 'inttree' ، به عنوان مثال: int_tree inttree int inttree = inttree ؛خالی_ tree = inttree ؛
• نوع پلی مورفیک نوعی است که توضیحات آن به جای انواع واقعی شامل پارامترها (متغیرهای نوع) است. تقریباً ، یک الگوی در C ++ چه خواهد بود. در اینجا شرح لیست نوع آلفا است که در آن لیست یک نوع چند شکل از arity 1 (به عنوان مثال ، وابسته به یک آرگومان واحد) است ، و آلفا یک متغیر نوع است که به عنوان پارامتر اختیاری سازنده (در بریس های فرفری) ظاهر می شود: alpha (لیست "آلفا) = لیست آلفا ؛nil = لیست آلفا ؛
• مقدار (کامپوزیت) نوع T هر دنباله ای از A* در قالب cont_num arg1 است. argn ، که در آن constr_num تعداد شاخص برخی از سازندگان C است که مقادیر نوع t را به خود اختصاص می دهد ، و arg_i مقدار Type T_i است که نوع آرگومان I-Th به سازنده c است. به عنوان مثال ، اجازه دهید Combinator int_tree دارای شماره شماره 17 باشد ، در حالی که Combinator Empty_tree دارای شماره 239 است. سپس ، به عنوان مثال ، مقدار نوع INTTREE ، به عنوان مثال ، 17 17 17 239 1 239 2 239 است که به راحتی به عنوان "int_tree" نوشته شده است. int_tree '' ottle_tree '1' خالی_tree '2' خالی_tree '. از دیدگاه یک زبان سطح بالا ، این int_tree (int_tree (خالی_تری) 1 (خالی_تری)) 2 (خالی_تری) است: inttree.
• طرحواره مجموعه ای از کلیه توضیحات نوع داده (کامپوزیت) است. این برای تعریف برخی از سیستم های توافق شده از انواع استفاده می شود.

انواع جعبه ای و لخت

• Boxed Type نوعی است که هر مقدار از آن با شماره سازنده شروع می شود. از آنجا که هر سازنده دارای یک نوع مقدار منحصر به فرد است ، شماره اول در هر مقدار از نوع جعبه ای به طور منحصر به فرد نوع خود را تعریف می کند. این تضمین می کند که انواع مختلف جعبه در کلیت ، یک سیستم هماهنگ از انواع را تشکیل می دهند. یک شناسه از نوع جعبه همیشه سرمایه گذاری می شود.
• نوع برهنه نوعی است که مقادیر آن حاوی شماره سازنده نیست ، که در عوض دلالت دارد. یک شناسه نوع لخت همیشه با نام سازنده ضمنی (و بنابراین ، با یک حرف کوچک شروع می شود) که ممکن است در قسمت جلوی آن با علامت درصد (٪) قرار بگیرد ، همزمان است. علاوه بر این ، اگر X نوع جعبه ای با بیش از یک سازنده واحد باشد ، ٪ x به نوع لخت مربوطه اشاره دارد. مقادیر یک نوع برهنه با مجموعه توالی های شماره به دست آمده با رها کردن شماره اول (یعنی شماره ، شماره شاخص سازنده خارجی) از مجموعه مقادیر نوع جعبه مربوطه (که نوع نتیجه سازنده انتخاب شده است) یکسان است. با شروع شماره شاخص سازنده انتخاب شده. به عنوان مثال ، 3 4 یک مقدار از نوع لخت int_couple است که با استفاده از int_couple int int = intcouple تعریف شده است. نوع جعبه مربوطه intcouple است. اگر 404 شماره شاخص سازنده برای int_couple باشد ، 404 3 4 مقدار برای نوع جعبه intcouple است که مطابق با مقدار نوع برهنه int_couple (همچنین به عنوان ٪ int_couple و ٪ intcouple شناخته می شود ؛ فرم دوم از نظر مفهومی ترجیح داده می شود اما طولانی تر است).

از نظر مفهومی ، فقط انواع جعبه باید در همه جا استفاده شود. با این حال ، برای سرعت و جمع و جور بودن ، باید از انواع لخت استفاده شود (به عنوان مثال ، مجموعه ای از 10،000 مقدار INT لخت 40،000 بایت طول دارد ، در حالی که مقادیر INT جعبه ای دو برابر فضای بیشتر طول می کشد ؛ بنابراین ، هنگام انتقال مجموعه بزرگی از شناسه های عدد صحیح، مثلاً استفاده از نوع int وکتور به جای وکتور int کارآمدتر است). علاوه بر این ، تمام انواع پایه (int ، طولانی ، دوتایی ، رشته) لخت هستند.

اگر یک نوع جعبه ای چند شکل از نوع arity r باشد ، این نیز در مورد هر نوع لخت مشتق شده نیز صادق است. به عبارت دیگر ، اگر کسی می توانست intcouple int alpha = intcouple alpha را تعریف کند ، پس از آن ، پس از آن ، intcouple به عنوان یک شناسه نیز می تواند یک نوع چند شکل از arity 1 در ترکیبات (و در نتیجه ، در سازنده و نوع) باشد. نمادهای Intcouple X ، ٪ (intcouple X) و ٪ intcouple X معادل هستند.

انواع پایه

انواع پایه هم به عنوان نسخه های برهنه (int ، طولانی ، دوتایی ، رشته) و به عنوان جعبه (int ، طولانی ، دوتایی ، رشته) وجود دارد. شناسه سازنده آنها همزمان با نام انواع لخت مربوطه است. توصیفات شبه آنها ظاهری زیر دارد:

int؟= int ؛طولانی؟= طولانی ؛دو برابر ؟= دو برابر ؛رشته؟= رشته ؛

در نتیجه ، به عنوان مثال ، شماره شاخص سازنده Int ، CRC32 رشته "int؟ = int" است.

مقادیر نوع لخت INT دقیقاً تمام توالی های تک عنصر است ، من. ه. اعداد بی ن-2^31 و 2^31-1 خود را در این مورد نشان می دهد. مقادیر نوع طولانی توالی های دو عنصر هستند که شماره های امضا شده 64 بیتی هستند (دوباره Endian دوباره). مقادیر نوع دوتایی ، مجدداً توالی های دو عنصر حاوی اعداد واقعی 64 بیتی در یک قالب دوتایی استاندارد هستند. و در آخر ، مقادیر رشته نوع بسته به طول L رشته در حال سریال متفاوت به نظر می رسند:

شبه قضایی

شبه بینی شیء "نوع" است که می تواند مقادیری را که متعلق به هر نوع جعبه ای در طرحواره است ، به خود اختصاص دهد. این کمک می کند تا به سرعت انواع مختلفی مانند لیست موارد تصادفی را بدون استفاده از انواع پلی مورفیک تعریف کنید. بهتر است از این توانایی سوءاستفاده نکنید زیرا منجر به استفاده از تایپ پویا می شود. با این وجود ، تصور ساختارهای داده ای که ما از PHP و JSON می شناسیم بدون استفاده از شبهوتیپ شیء دشوار است.

توصیه می شود در هر زمان ممکن از typedobject استفاده کنید:

شی X: مقدار نوع: x = typedobject ؛

انواع کامپوزیت داخلی: بردارها و آرایه های انجمنی

شبهوتیپ پلی مورفیک بردار T یک "نوع" است که مقدار آن دنباله ای از مقادیر هر نوع T ، چه جعبه ای یا لخت است.

بردار # [t] = بردار t ؛

سریال سازی همیشه از همان سازنده "بردار" استفاده می کند (const 0x1cb5c415 = crc32 ("بردار t: نوع # [t] = بردار t") که به مقدار خاص متغیر نوع t وابسته نیست. مقدار بردار tنوع شماره شاخص شماره سازنده مربوطه و به دنبال آن n ، تعداد عناصر موجود در بردار و سپس با مقادیر n نوع t است. مقدار پارامتر اختیاری t در سریال سازی دخیل نیست زیرا از آن حاصل می شودنوع نتیجه (همیشه قبل از deserialization شناخته شده است).

pseudotypes polymorphic inthash t و strhash t آرایه های انجمنی نقشه برداری عدد صحیح و کلیدهای رشته ای برای مقادیر نوع t هستند. آنها در واقع بردارهایی هستند که حاوی 2 عکس لخت (int ، t) یا (رشته ، t) هستند:

justonint int t = jountint t ؛INTHASH (بردار ٪ (TUNTINT T)) = INTHASH T ؛string coplest t = couplest t ؛Strhash (بردار ٪ (COUPLEST T)) = Strhash T ؛

در این حالت علامت درصد ، به این معنی است که یک نوع لخت که مطابق با نوع جعبه در پرانتز است ، گرفته می شود. نوع جعبه در سوال نباید بیش از یک سازنده واحد باشد ، هر مقادیر پارامترها.

کلیدها ممکن است مرتب شوند یا به ترتیب دیگری باشند (مانند آرایه های PHP). برای آرایه های انجمنی با کلیدهای مرتب شده ، از intsortedhash یا strsortedhash alias استفاده می شود:

intsortedhash (inthash t) = intsortedhash t ؛Strsortedhash (Strhash T) = StrsortedHash T ؛

سازه های نوع چند شکل

سازنده یک نوع پلی مورفیک به انواع خاصی که از نوع پلی مورفیک استفاده می شود بستگی ندارد. هنگامی که محاسبه می شود ، پارامترهای اختیاری (به طور معمول حاوی متغیرهای نوع و در بریس های فرفری قرار می گیرند) از اختیاری متوقف می شوند (بریس های فرفری برداشته می شوند) ، و علاوه بر آن ، تمام پرانتز نیز حذف می شوند. از این رو،

بردار # [t] = بردار t ؛

مطابق با شماره سازنده CRC32 ("بردار T: نوع # [t] = بردار t") = 0x1CB5C415. در طول سریال سازی (DE) ، مقادیر خاص متغیر اختیاری T از نوع نتیجه (یعنی شیء سریالی یا deserialized) حاصل می شود که همیشه شناخته شده است ، و هرگز به صراحت سریال نمی شوند.

پیش از این ، باید مشخص شد که کدام متغیر خاص هر نوع چند شکل برای آن اعمال می شود. برای انجام این کار ، سیستم نوع از رشته های فرم استفاده می کند

polymorphic_type_name type_1. type_n ؛

بردار int ؛رشته بردار ؛شیء بردار ؛

اکنون آنها نادیده گرفته می شوند.

در این حالت ، شبهایپ شیء با استفاده از شیء بردار برای ذخیره لیست های هر چیزی (مقادیر انواع جعبه) اجازه می دهد. از آنجا که انواع لخت در هنگام کوتاه بودن کارآمد هستند ، در عمل بعید است که موارد پیچیده تر از موارد ذکر شده در بالا لازم باشد.

نام میدانی

بگذارید بگوییم که ما باید کاربران را به عنوان سه گانه حاوی یک عدد صحیح (شناسه کاربر) و دو رشته (نام های اول و نام خانوادگی) معرفی کنیم. ساختار داده های لازم ، رشته سه گانه ، رشته ، رشته ای است که ممکن است به شرح زیر اعلام شود:

int int string string = کاربر ؛

از طرف دیگر ، یک گروه ممکن است توسط یک سه گانه مشابه متشکل از شناسه گروهی ، نام و توضیحات آن توصیف شود:

رشته int رشته رشته = گروه ؛

برای اینکه تفاوت بین کاربر و گروه روشن باشد ، مناسب است که اسامی را به برخی یا همه زمینه ها اختصاص دهید:

شناسه کاربر: int first_name: string last_name: string = user ؛شناسه گروه: int عنوان: توضیحات رشته: رشته = گروه ؛

اگر با داشتن سوابق با برخی از زمینه های اضافی که به آن اضافه شده است ، نوع کاربر باید در زمان بعدی گسترش یابد ، می تواند به شرح زیر انجام شود:

iderv2 id: int unread_messages: int first_name: string last_name: string in_groups: int int = user ؛

گذشته از موارد دیگر ، این رویکرد به تعریف نقشه های صحیح بین زمینه هایی که متعلق به سازندگان مختلف از یک نوع هستند ، کمک می کند ، بین آنها و همچنین تبدیل مقادیر نوع به یک آرایه انجمنی با کلیدهای رشته ای تبدیل می شود (در صورت تعریف نام ، در صورت تعریف ، گزینه های طبیعی برای آنها هستندچنین کلیدهایی)