إن محرري النصوص المعاصرين ليسوا قادرين فقط على التنبيه وعدم مغادرة البرنامج. اتضح أن التمثيل الغذائي المعقد للغاية يغلي بداخلها. هل تريد أن تعرف ما هي الحيل التي يتم إجراؤها لإعادة حساب الإحداثيات بسرعة ، وكيف يتم إرفاق الأنماط والأطواق والأغلفة البرمجية بالنص وكيف يتم تحديثه بالكامل ، وما علاقة هيكل البيانات الوظيفية وقائمة انتظار الأولوية به ، بالإضافة إلى كيفية خداع المستخدم - مرحبًا بالقط!



تستند المقالة على تقرير Alexei Kudryavtsev مع Joker 2017. وقد كان Alexei يكتب Intellij IDEA في JetBrains منذ حوالي 10 سنوات. تحت القطع ستجد نص الفيديو والنص من التقرير.

هياكل البيانات داخل برامج تحرير النصوص

لفهم كيفية عمل المحرر ، دعنا نكتبه.



هذا كل شيء ، أبسط محرر جاهز.

داخل المحرر ، من الأسهل تخزين النص في مجموعة من الأحرف ، أو ما هو نفسه (من حيث تنظيم الذاكرة) ، في فئة Java StringBuffer. للحصول على بعض الأحرف عن طريق الإزاحة ، نسمي طريقة StringBuffer.charAt (i). ولإدراجها في الحرف الذي كتبناه على لوحة المفاتيح ، نطلق على أسلوب StringBuffer.insert () ، الذي يدرج الحرف في مكان ما في المنتصف.

ما هو أكثر إثارة للاهتمام ، على الرغم من كل بساطة وحمق هذا المحرر ، هو أفضل فكرة يمكنك ابتكارها. إنه بسيط وسريع دائمًا.

لسوء الحظ ، تنشأ مشكلة الحجم مع هذا المحرر. تخيل أننا قمنا بطباعة الكثير من النصوص فيه وسندرج حرفًا آخر في المنتصف. سيحدث ما يلي. نحن بحاجة ماسة إلى تحرير بعض المساحة لهذه الرسالة عن طريق تحريك جميع الأحرف الأخرى إلى الأمام. للقيام بذلك ، نقوم بتحويل هذه الرسالة بموضع واحد ، ثم التالي وما إلى ذلك ، حتى نهاية النص.

إليك كيف ستبدو في الذاكرة:



إن تحويل كل هذا العدد الكبير من وحدات الميغابايت ليس جيدًا جدًا: إنه بطيء. بالطبع ، بالنسبة للكمبيوتر الحديث ، هذه مسألة تافهة - نوع من الميغابايت مثير للشفقة للتحرك ذهابًا وإيابًا. ولكن لتغيير النص النشط للغاية ، يمكن أن يكون هذا ملحوظًا.

لحل مشكلة إدراج حرف في الوسط ، توصل منذ وقت طويل إلى حل بديل يسمى "Gap Buffer".

العازلة الفجوة

الفجوة هي الفجوة. العازلة ، كما قد تتخيل ، عازلة. إن بنية بيانات Gap Buffer عبارة عن مخزن مؤقت فارغ نحتفظ به في منتصف نصنا ، في حالة الضرورة. إذا احتجنا إلى طباعة شيء ما ، فإننا نستخدم هذا المخزن المؤقت النصي الصغير للكتابة السريعة.



تغيرت بنية البيانات قليلاً - بقيت الصفيف في مكانه ، ولكن ظهرت مؤشرين: في بداية المخزن المؤقت وفي نهايته. لأخذ حرف من المحرر عند بعض الإزاحة ، نحتاج إلى فهم ما إذا كان قبل أو بعد هذا المخزن المؤقت وتصحيح الإزاحة قليلاً. ولإدراج حرف ، نحتاج أولاً إلى نقل Gap Buffer إلى هذا المكان وملئه بهذه الشخصيات. وبالطبع ، إذا تجاوزنا حاجزنا المؤقت ، فسنعيد إنشائه بطريقة أو بأخرى. هكذا تبدو في الصورة.



كما ترى ، ننتقل أولاً لفترة طويلة على مخزن مؤقت صغير (مستطيل أزرق) إلى موقع التحرير (ببساطة نقوم بتبديل الأحرف من حافتيها اليسرى واليمنى على التوالي). ثم نستخدم هذا المخزن المؤقت ، ونكتب الأحرف هناك.

كما ترون ، لا توجد حركة للميغابايت من الأحرف ، والإدراج سريع جدًا ، ولوقت ثابت ، ويبدو أن الجميع سعداء. يبدو أن كل شيء على ما يرام ، ولكن إذا كان معالجنا بطيئًا جدًا ، فسيضيع وقت ملحوظ جدًا في تحريك المخزن المؤقت للنص والعودة للأمام وللخلف. كان هذا ملحوظًا بشكل خاص في وقت ميغاهيرتز صغير جدًا.

طاولة قطعة

في ذلك الوقت فقط ، قامت شركة تسمى Microsoft بكتابة محرر نصوص Word. قرروا تطبيق فكرة أخرى لتسريع عملية التحرير المسماة "قطعة الطاولة" ، أي "قطعة الطاولة". واقترحوا حفظ نص المحرر في نفس أبسط مجموعة من الأحرف ، والتي لن تتغير ، ووضع جميع التغييرات في جدول منفصل عن هذه القطع المحررة للغاية.



وبالتالي ، إذا كنا بحاجة إلى العثور على بعض الأحرف عن طريق الإزاحة ، فنحن بحاجة إلى العثور على هذه القطعة التي قمنا بتحريرها واستخراج هذا الحرف منها ، وإذا لم تكن هناك ، فانتقل إلى النص الأصلي. يصبح إدراج رمز أسهل ، نحتاج فقط إلى إنشاء وإضافة هذه القطعة الجديدة إلى الجدول. إليك كيف تبدو في الصورة:



هنا أردنا إزالة المساحة عند الإزاحة 5. للقيام بذلك ، نضيف قطعتين جديدتين إلى طاولة القطع: واحدة تشير إلى الجزء الأول ("Bummer") ، والثانية تشير إلى الجزء بعد التحرير ("الأغنام"). اتضح أن الفجوة بينهما تختفي ، يتم لصق هاتين القطعتين معًا ، ونحصل بالفعل على نص جديد بدون مسافة: "Oblomovtsy". ثم نضيف النص الجديد ("المعاناة من Oblomovism") إلى النهاية. استخدم مخزنًا مؤقتًا إضافيًا وأضف شريحة جديدة إلى جدول القطع الذي يشير إلى أحدث نص تمت إضافته.

كما ترون ، لا توجد حركة ذهابا وإيابا ، كل النص يبقى في مكانه. الأخبار السيئة هي أنه من الصعب الوصول إلى الرمز ، لأن الفرز عبر كل هذه القطع صعب جدًا.

لتلخيص.

ما هو جيد حول قطعة الجدول :

• تضمين سريع ؛
• سهل التراجع ؛
• إلحاق فقط.

ما هو السيئ:

• من الصعب للغاية الوصول إلى مستند ؛
• من الصعب للغاية تنفيذها.

دعونا نرى من نستخدم عادة ما.

يستخدم NetBeans و Eclipse و Emacs فجوة الفجوة - أحسنت! السادس لا يزعج ويستخدم فقط قائمة من الخطوط. يستخدم Word الجدول قطعة (لقد وضعوا مؤخرًا أنواعهم القديمة ويمكنك حتى فهم شيء ما).

الذرة أكثر إثارة. حتى وقت قريب ، لم يهتموا واستخدموا قائمة خطوط JavaScript. ثم قرروا إعادة كتابة كل شيء في C ++ وأكوام بنية معقدة إلى حد ما ، والتي تبدو مشابهة لقطعة الطاولة. لكن هذه القطع لا يتم تخزينها في القائمة ، ولكن في الشجرة ، وفي ما يسمى شجرة التباعد - هذه شجرة يتم ضبطها ذاتيًا عند إدخالها فيها ، بحيث تكون الإدخالات الأخيرة أسرع. فعلوا شيء معقد للغاية.

ماذا تستخدم Intellij IDEA؟
لا ، ليس فجوة عازلة. لا ، أنت مخطئ أيضًا ، وليس طاولة قطع.
نعم ، صحيح تمامًا ، دراجتك الخاصة.

والحقيقة هي أن متطلبات IDE لتخزين النص تختلف قليلاً عن تلك الموجودة في محرر النصوص العادي. يحتاج IDE إلى دعم للعديد من الأشياء الصعبة مثل القدرة التنافسية ، أي الوصول الموازي إلى النص من المحرر. على سبيل المثال ، حتى تتمكن العديد من المخبوزات المختلفة من قراءتها والقيام بشيء ما. (الاستقصاء عبارة عن جزء صغير من التعليمات البرمجية يوزع البرنامج بطريقة أو بأخرى - على سبيل المثال ، البحث عن الأماكن التي ترمي NullPointerException). يحتاج IDE أيضًا إلى دعم إصدار النص القابل للتحرير. توجد العديد من الإصدارات في وقت واحد في الذاكرة أثناء العمل مع مستند بحيث تستمر هذه العمليات الطويلة في تحليل الإصدار القديم.

المشاكل

القدرة التنافسية / الإصدار

من أجل الحفاظ على التوازي ، عادة ما يتم لف عمليات النص في "متزامن" ، أو في أقفال قراءة / كتابة. لسوء الحظ ، هذا لا يتطور بشكل جيد للغاية. نهج آخر هو نص غير قابل للتغيير ، أي مستودع نص غير قابل للتغيير.



إليك ما يبدو عليه المحرر مع مستند ثابت كبنية بيانات داعمة.

كيف يعمل هيكل البيانات؟

بدلاً من مجموعة من الأحرف ، سيكون لدينا كائن جديد من النوع ImmutableText ، الذي يخزن النص في شكل شجرة ، حيث يتم تخزين سلاسل فرعية صغيرة في الأوراق. عند الوصول إلى بعض الإزاحة ، يحاول الوصول إلى الورقة السفلية في هذه الشجرة ، وسيطلب منه بالفعل الرمز الذي كنا نشير إليه. وعندما تقوم بإدراج نص ، يقوم بإنشاء شجرة جديدة وحفظها في المكان القديم.



على سبيل المثال ، لدينا مستند يحتوي على النص "خالٍ من السعرات الحرارية". يتم تنفيذه كشجرة مع ورقتين من الاستبدالات "Demon" و "ذات السعرات الحرارية العالية". عندما نريد إدراج السطر "جميل" في المنتصف ، يتم إنشاء نسخة جديدة من وثيقتنا. وبالتحديد ، يتم إنشاء جذر جديد ، تم إرفاق ثلاث أوراق به بالفعل: "شيطان" ، "كافي" و "عالي السعرات الحرارية". علاوة على ذلك ، قد تشير اثنتان من هذه الأوراق الجديدة إلى الإصدار الأول من وثيقتنا. وبالنسبة للورقة التي أدخلنا فيها السطر "جميل" ، تم تخصيص قمة جديدة. هنا يتوفر كل من الإصدار الأول والإصدار الثاني في نفس الوقت وكلهما غير قابل للتغيير وغير قابل للتغيير. كل شيء يبدو جيدًا.

من يستخدم ما هي الهياكل الصعبة؟



على سبيل المثال ، في جنوم ، تستخدم بعض أدواتها القياسية هيكلًا يسمى حبل. يستخدم Xi-Editor ، المحرر الرائع الجديد من Raf Levien ، Persistent Rope. وتستخدم Intellij IDEA هذه الشجرة غير القابلة للتغيير. وراء كل هذه الأسماء ، في الواقع ، هو إلى حد ما نفس هيكل البيانات مع تمثيل يشبه شجرة النص. باستثناء أن GtkTextBuffer يستخدم حبل قابل للطي ، أي شجرة ذات رؤوس قابلة للتغيير ، و Intellij IDEA و Xi-Editor - Immutable.

الشيء التالي الذي يجب مراعاته عند تطوير مستودع الأحرف في IDEs الحديثة يسمى multicats. تتيح لك هذه الميزة الطباعة في عدة أماكن في وقت واحد ، باستخدام العديد من العربات.



يمكننا طباعة شيء ما وفي الوقت نفسه في عدة أماكن من المستند ، نقوم بإدراج ما قمنا بطباعته هناك. إذا نظرنا إلى الكيفية التي تتفاعل بها هياكل البيانات لدينا ، والتي قمنا بفحصها ، مع العديد من الأنظمة ، سنرى شيئًا مثيرًا للاهتمام.



إذا أدرجنا شخصية في أول محرر بدائي لدينا ، فسيستغرق الأمر بالطبع وقتًا خطيًا لنقل مجموعة من الشخصيات ذهابًا وإيابًا. هذا مكتوب كـ O (N). بالنسبة للمحرر الذي يعتمد على Gap Buffer ، في المقابل ، يلزم وقت ثابت ، والذي صاغ له.

بالنسبة للشجرة غير القابلة للتغيير ، يعتمد الوقت على اللوغاريتمات على الحجم ، لأنه يجب عليك أولاً الانتقال من أعلى الشجرة إلى أوراقها - هذا هو اللوغاريتم ، ثم بالنسبة لجميع القمم على المسار لإنشاء رؤوس جديدة للشجرة الجديدة - هذا هو اللوغاريتم مرة أخرى. يتطلب قطعة الطاولة أيضا ثابت.
لكن كل شيء يتغير قليلاً إذا حاولنا قياس وقت إدخال شخصية في محرر مع عربات متعددة ، أي إدخال في وقت واحد في عدة أماكن. للوهلة الأولى ، يبدو أن الوقت يتزايد بشكل نسبي بعامل C - عدد الأماكن التي يتم إدخال الرمز فيها. هذا هو بالضبط ما يحدث ، باستثناء Gap Buffer. في قضيته ، يزيد الوقت ، بدلاً من C مرة ، بشكل غير متوقع بعض مرات C * L غير المفهومة ، حيث L هي متوسط ​​المسافة بين العربات. لماذا يحدث هذا؟

تخيل أننا بحاجة إلى إدراج السطر "تشغيل" في مكانين في وثيقتنا.



هذا ما يحدث في المحرر في هذا الوقت.

• إنشاء فجوة عازلة في المحرر (مستطيل أزرق صغير في الصورة) ؛
• نبدأ عربتين (خطوط عمودية سوداء جريئة) ؛
• نحن نحاول الطباعة ؛
• إدراج فاصلة في المخزن المؤقت للفجوة ؛
• يجب عليك الآن إدخالها في مكان الحامل الثاني ؛
• للقيام بذلك ، نحتاج إلى نقل عازل الفجوة إلى موضع النقل التالي ؛
• بصمة فاصلة في المركز الثاني ؛
• تحتاج الآن إلى إدخال الحرف التالي في موضع الحامل الأول ؛
• وعلينا أن ندفع فجوة العازلة.
• أدخل الحرف "n" ؛
• وننقل عازلنا الذي عانى طويلا إلى مكان النقل الثاني ؛
• نضيف "ن" لدينا هناك ؛
• انقل المخزن المؤقت إلى الخلف لإدراج الحرف التالي.

تشعر أين يذهب كل شيء؟

نعم ، اتضح أنه بسبب هذه الحركات العديدة للعازلة ذهابًا وإيابًا ، يزداد إجمالي وقتنا. بصراحة ، ليس الأمر مروعًا بشكل مباشر لأنها زادت - نقل الميغا بايت المثير للشفقة ، غيغابايت ذهابًا وإيابًا لجهاز كمبيوتر حديث ليست مشكلة ، ولكن من المثير للاهتمام أن بنية البيانات هذه تعمل بشكل مختلف جذريًا في حالة تعدد القطط.

خطوط كثيرة جدا؟ LineSet!

ما المشكلات الأخرى الموجودة في محرر النصوص العادي؟ إن أصعب مشكلة هي التمرير ، أي إعادة رسم المحرر أثناء نقل حامل الخراطيش إلى السطر التالي.



عندما يتم تمرير المحرر ، نحتاج أن نفهم من أي سطر ، من أي رمز نحتاجه لبدء رسم النص في نافذتنا الصغيرة. للقيام بذلك ، نحتاج إلى فهم الخط الذي يتوافق مع أي إزاحة بسرعة.



هناك واجهة واضحة لهذا ، عندما نحتاج إلى فهم إزاحته في النص برقم السطر. والعكس بالعكس ، بالإزاحة في النص لفهم الخط الذي هو عليه. كيف يمكن القيام بذلك بسرعة؟

على سبيل المثال ، مثل هذا:

قم بتنظيم هذه الخطوط في شجرة ووضع علامة على كل قمة لهذه الشجرة عن طريق تغيير بداية السطر وتحريك نهاية السطر. وبعد ذلك ، من أجل فهم الإزاحة التي يقع فيها الخط ، ما عليك سوى إجراء بحث لوغاريتمي في هذه الشجرة والعثور عليه.



طريقة أخرى أسهل.

اكتب في الجدول إزاحة بداية السطور ونهاية السطور. وبعد ذلك ، للعثور على إزاحة البداية والنهاية برقم السطر ، ستحتاج إلى الوصول إلى الفهرس.



من المثير للاهتمام ، في العالم الحقيقي ، يتم استخدام كلتا الطريقتين.



على سبيل المثال ، يستخدم Eclipse مثل هذا الهيكل الخشبي الذي ، كما ترون ، يعمل في وقت لوغاريتمي للقراءة والتحديث. وتستخدم IDEA بنية جدول ، حيث تكون القراءة ثابتة بالنسبة لها ، وهي انعكاس فهرس في جدول ، لكن إعادة البناء بطيئة إلى حد ما ، لأنك تحتاج إلى إعادة بناء الجدول بأكمله عند تغيير طول الصف.

هل مازال لديك العديد من الخطوط طيّات!

ما هو الشيء السيئ الذي يتعثر عبر محرري النصوص؟ على سبيل المثال ، طي. هذه أجزاء من النص يمكنك "طيها" وعرض شيء آخر بدلاً من ذلك.



تخفي هذه النقاط على خلفية خضراء في الصورة الكثير من الرموز خلفنا ، ولكن إذا لم نرغب في النظر إليها (كما هو الحال ، على سبيل المثال ، أطول مستندات جافا مملة أو قوائم الاستيراد) ، فإننا نخفيها ، وننهارها القطع.

وهنا مرة أخرى تحتاج إلى فهم متى تنتهي ومتى تبدأ المنطقة التي نحتاج إلى إظهارها ، وكيف نقوم بتحديثها كلها بسرعة؟ كيف يتم تنظيم ذلك ، سأخبرنا بعد ذلك بقليل.

طوابير طويلة جدا؟ التفاف لينة!

أيضا ، لا يمكن للمحررين الحديثين العيش بدون غلاف ناعم. تظهر الصورة أن المطور قام بفتح ملف JavaScript بعد تصغيره وأسفه على الفور. خط جافا سكريبت الضخم هذا ، عندما نحاول عرضه في المحرر ، لن يتناسب مع أي شاشة. لذلك ، يؤدي الالتفاف الناعم إلى تمزيقه بالقوة إلى عدة خطوط ويدفعه إلى الشاشة.
كيف يتم تنظيمه - فيما بعد.

جمال قليل جدا

وأخيرًا ، أرغب أيضًا في جلب الجمال إلى محرري النصوص. على سبيل المثال ، قم بتمييز بعض الكلمات. في الصورة أعلاه ، يتم تمييز الكلمات الرئيسية باللون الأزرق الغامق ، وبعض الطرق الثابتة بخط مائل ، وبعض التعليقات التوضيحية - أيضًا بلون مختلف.

فكيف ما زلت تقوم بتخزين ومعالجة الطيات والأغطية الناعمة واللمحات؟
اتضح أن كل هذا ، من حيث المبدأ ، هو نفس المهمة.

القليل من الجمال؟ تمييز النطاق!

لدعم كل هذه الميزات ، كل ما نحتاج إلى القيام به هو التمسك ببعض سمات النص عند إزاحة معينة في النص ، على سبيل المثال ، اللون أو الخط أو النص للطي. علاوة على ذلك ، يجب تحديث سمات النص هذه طوال الوقت في هذا المكان حتى تتمكن من البقاء على قيد الحياة في جميع أنواع عمليات الإدراج والحذف.

كيف يتم تنفيذ هذا عادة؟ بطبيعة الحال ، في شكل شجرة.

المشكلة: الكثير من الجمال؟ شجرة الفاصل الزمني!

على سبيل المثال ، لدينا هنا العديد من الإبرازات الصفراء التي نريد الاحتفاظ بها في النص. نضيف فترات هذه الإبرازات إلى شجرة البحث ، ما يسمى شجرة الفواصل الزمنية. هذه هي نفس شجرة البحث ، ولكنها أكثر صعوبة لأننا بحاجة إلى تخزين الفواصل الزمنية بدلاً من الأرقام.

وبما أن هناك فترات صحية وصغيرة على حد سواء ، فإن كيفية فرزها ومقارنتها مع بعضها البعض ووضعها في شجرة هي مهمة غير تافهة إلى حد ما. على الرغم من أنها معروفة على نطاق واسع في علوم الكمبيوتر. ثم انظر بطريقة ما إلى وقت فراغك كيف يعمل. لذا ، نأخذ كل فواصلنا ونضعها في شجرة ، ثم يؤدي كل تغيير في النص في مكان ما في المنتصف إلى تغيير لوغاريتمي في هذه الشجرة. على سبيل المثال ، يجب أن يؤدي إدراج حرف إلى تحديث جميع الفواصل الزمنية إلى يمين ذلك الحرف. للقيام بذلك ، نجد جميع القمم السائدة لهذا الرمز ونشير إلى أنه يجب تحريك جميع رؤوسهم رمزًا واحدًا إلى اليمين.

هل ما زلت تريد الجمال؟ الحروف المركبة!

لا يزال هناك مثل هذا الشيء الرهيب - الحروف المركبة ، والتي أود أيضًا دعمها. هذه جماليات مختلفة ، مثل علامة "! =" يتم رسمها في شكل حرف رسومي كبير "لا يساوي" وما إلى ذلك. لحسن الحظ ، نحن هنا نعتمد على آلية التأرجح لدعم هذه الحروف المركبة. وفي تجربتنا ، يبدو أنه يعمل بأبسط طريقة. داخل الخط ، يتم تخزين قائمة بكل هذه الأزواج من الأحرف ، والتي ، عند دمجها معًا ، تشكل نوعًا من الأربطة الصعبة. بعد ذلك ، عند رسم الخط ، يتكرر Swing ببساطة فوق كل هذه الأزواج ، ويجد الأزواج اللازمة ويرسمها وفقًا لذلك. إذا كان لديك الكثير من الحروف المركبة في الخط ، فإن عرضه سيتباطأ نسبيًا على ما يبدو.

انقلاب الفرامل

والأهم من ذلك - هناك مشكلة أخرى تمت مواجهتها في المحررين المعقدين المعاصرين وهي تحسين إمكانات البقشيش ، أي الضغط على المفاتيح وعرض النتيجة.



إذا دخلت إلى Intellij IDEA ورأيت ما يحدث عند الضغط على أحد الأزرار ، فقد حدث الرعب التالي:

• بنقرة زر واحدة ، نحتاج إلى معرفة ما إذا كنا في نافذة الإكمال المنبثقة لإغلاق القائمة لإكمالها ، على سبيل المثال ، إذا قمنا بكتابة بعض "Enter".
• تحتاج إلى معرفة ما إذا كان الملف خاضعًا لنظام تحكم إصدار صعب ، مثل Perforce ، الذي يحتاج إلى اتخاذ بعض الإجراءات لبدء التحرير.
• تحقق مما إذا كان هناك أي منطقة خاصة في المستند لا يمكن طباعتها ، مثل بعض النصوص التي تم إنشاؤها تلقائيًا.
• إذا تم حظر المستند بواسطة عملية لم تنته ، فأنت بحاجة إلى إكمال التنسيق ، ثم المتابعة فقط.
• injected-, , , - .
• auto popup handler, , , .
• info , , . selection remove, selection , . selection , .
• typed handler, , .
• .
• undo, virtual space' write action.
• , .

!

, , . , . , listener , , - . editor view. - listener'.

, , - DocumentListener?

Editor.documentChanged() :

• error stripe;
• gutter size, ;
• editor component size, ;
• ;
• soft wrap, ;
• repaint().

repaint() — Swing, . , Repaint Swing.

- , repaint , :



paint-, , .

, , ?



, , . Intellij IDEA .



, - - , , , . ! , , , - — ! , - . . «Zero latency typing».

— .

? , — , Google Docs - - .

:

• ;
• .

, , .

- . , , . . — , «intention preservation». , - , , , . — . , - , .

Operation transformation

, , «operation transformation». . , - : , . Operation transformation . , , , - . , . , - . , , .

, , , . «TP2 puzzle».



- , , . , Operation transformation , , , («»). («»). , . , Operation transformation, - .

, Google Docs, Google Wave - Etherpad. Operation transformation .

Conflict-free replicated data type

: « , OT!» , , . , , , , 100% . «CRDT» (Conflict-free replicated data type).



, , . , , , . , . - ( ), () ( ).



?

نعم , G-counter', , . , . «+1» , «+1» , , — «2». , , . G-counter, , . G-counter, . , , . . — . , CRDT. , .

Conflict-free replicated inserts

, , , . , , .

, , - - , , , , . , , , , . , , , , 2 «», , «» «» «».

Conflict-free replicated deletes

. , , , - . , , . , , , .
, .

Conflict-free replicated edits

, , CRDT - , , Xi-Editor, Fuchsia. , , .

Zipper

, «Zipper». , , . , , . , ( «» , , « »). , - . , - , . Zipper.

, . .



Zipper , (« »). Zipper' . — . (), , . , Zipper, - , . , , , ( ). , ( ). , . , .

, .

? -, , , , . , , . -, , . . شكرا لك

→
→

المراجع

Zipper data structure
CRDT in Xi Editor



, Visual Studio Code editor Piece Table .
, - .

هل تريد تقارير أكثر قوة ، بما في ذلك Java 11؟ ثم نحن في انتظارك في جوكر 2018 . المتحدثون هذا العام: جوش لونغ ، وجون ماكلين ، وماركوس هيرث ، وروبرت شولت وغيرهم من المتحدثين الرائعين بنفس القدر. هناك 17 يوما متبقية قبل المؤتمر. تذاكر على الموقع.