अपने ब्राउज़र को खरोंच से विकसित करें। भाग एक: एच.टी.एम.एल.

सभी को नमस्कार!

हम ब्राउज़र इंजन के विकास पर लेखों की श्रृंखला जारी रखते हैं।

इस लेख में मैं आपको बताऊंगा कि DOM के साथ सबसे तेज HTML पार्सर कैसे बनाया जाता है। हम HTML विनिर्देश को देखेंगे और HTML को पार्स करते समय प्रदर्शन और संसाधन खपत के बारे में बुरा क्यों है।

इस विषय के साथ, मैंने पिछले HighLoad ++ पर सूचना दी। हर कोई सम्मेलन में शामिल नहीं हो सकता है, साथ ही लेख में अधिक विवरण हैं।

मुझे लगता है कि पाठक को HTML का मूल ज्ञान है: टैग, नोड्स, तत्व, नाम स्थान।

HTML विनिर्देशन

इससे पहले कि आप HTML पार्सर के कार्यान्वयन पर स्पर्श करना शुरू करें, आपको यह समझने की आवश्यकता है कि HTML विनिर्देशों को क्या मानना ​​है।

दो HTML विनिर्देशन हैं:

1. WHATWG
   
   • Apple, Mozilla, Google, Microsoft
2. W3C
   
   • कंपनियों की बड़ी सूची

स्वाभाविक रूप से, यह पसंद उद्योग के नेताओं - WHATWG पर गिरी। लिविंग स्टैंडर्ड, बड़ी कंपनियों में से प्रत्येक अपने स्वयं के ब्राउज़र / ब्राउज़र इंजन के साथ।

अद्यतन: दुर्भाग्य से, विनिर्देशों के दिए गए लिंक रूस से नहीं खुलते हैं। जाहिर है, तार के साथ "युद्ध की गूंज"।

HTML पार्सिंग प्रक्रिया

HTML ट्री बनाने की प्रक्रिया को चार भागों में विभाजित किया जा सकता है:

1. विकोडक
2. पूर्व उपचार
3. tokenizer
4. एक पेड़ का निर्माण

हम प्रत्येक चरण को अलग-अलग मानते हैं।

विकोडक

टोकनधारक यूनिकोड वर्ण (कोड पॉइंट) को इनपुट के रूप में स्वीकार करता है। तदनुसार, हमें वर्तमान बाइट स्ट्रीम को यूनिकोड वर्ण में बदलने की आवश्यकता है। ऐसा करने के लिए, एन्कोडिंग विनिर्देश का उपयोग करें।

यदि हमारे पास अज्ञात एन्कोडिंग (कोई HTTP हेडर) के साथ HTML नहीं है, तो डिकोडिंग शुरू होने से पहले हमें इसे निर्धारित करने की आवश्यकता है। ऐसा करने के लिए, हम एन्कोडिंग सूँघने वाले एल्गोरिथ्म का उपयोग करेंगे।

यदि बहुत संक्षेप में, एल्गोरिथ्म का सार यह है कि हम बाइट स्ट्रीम से 500 या पहले 1024 इंतजार करते हैं और इसकी एन्कोडिंग को निर्धारित करने के लिए प्रीस्कैन एक बाइट स्ट्रीम एल्गोरिदम चलाते हैं जो कि http-equiv , content या charset साथ <meta> को खोजने की कोशिश करता है। समझें कि HTML डेवलपर ने क्या संकेत दिया।

Encoding विनिर्देश ब्राउज़र इंजन द्वारा समर्थित एन्कोडिंग के न्यूनतम सेट को निर्धारित करता है (कुल मिलाकर 21): UTF-8, ISO-8859-2, ISO-8859-7, ISO-8859-8, windows-874, windows-1250, windows-1251, विंडोज़ -1252, विंडो -1254, विंडो -1255, विंडो -1256, विंडो -1257, विंडो -1258, gb18030, Big5, ISO-2022-JP, Shift_JIS, EUC-KR, UTF-16BE, UTF-16LE और x-user से परिभाषित।

पूर्व उपचार

यूनिकोड वर्णों में बाइट्स को डीकोड करने के बाद, हमें "क्लीन अप" करने की आवश्यकता है। अर्थात्, एक कैरिज रिटर्न कैरेक्टर ( \r \n ) के साथ एक लाइन फीड कैरेक्टर ( \n ) के बाद सभी कैरिज रिटर्न कैरेक्टर ( \r ) को बदलें। फिर, सभी कैरेज़ रिटर्न वर्णों को एक नई वर्ण ( \n ) से बदलें।

इसलिए विनिर्देश में वर्णित है। अर्थात, \r\n => \r , \r => \n ।

लेकिन, वास्तव में, कोई भी नहीं करता है। इसे आसान बनाएं:

यदि आपको एक गाड़ी वापसी चरित्र ( \r ) मिलता है, तो यह देखने के लिए देखें कि क्या कोई पंक्ति फ़ीड वर्ण ( \n ) है। यदि वहाँ है, तो हम दोनों वर्णों को पंक्ति फ़ीड वर्ण ( \n ) में बदलते हैं, यदि नहीं, तो हम केवल प्रथम वर्ण ( \r ) को पंक्ति फ़ीड ( \n ) में बदलते हैं।

यह प्रारंभिक डेटा प्रोसेसिंग को पूरा करता है। हां, आपको बस गाड़ी के वापसी के प्रतीकों से छुटकारा पाने की आवश्यकता है ताकि वे टोकनधारक में न पड़ें। टोकनधारक उम्मीद नहीं करता है और यह नहीं जानता कि गाड़ी के वापसी चिन्ह का क्या करना है।

पार्सिंग त्रुटियाँ

ताकि भविष्य में कोई सवाल न हो, आप तुरंत बताएं कि एक क्या ( parse error )।

वास्तव में कुछ भी गलत नहीं है। यह गलत लगता है, लेकिन वास्तव में यह सिर्फ एक चेतावनी है कि हम एक की उम्मीद कर रहे थे, लेकिन हमारे पास एक और है।

पार्सिंग त्रुटि डेटा प्रोसेसिंग या ट्री बिल्डिंग को रोक नहीं पाएगी। यह एक संदेश है जो संकेत देता है कि हमारे पास वैध HTML नहीं है।

पार्सग त्रुटि सरोगेट जोड़े, \0 , गलत टैग स्थान, गलत <!DOCTYPE> और सभी प्रकार की अन्य चीजों के लिए प्राप्त की जा सकती है।

वैसे, कुछ पार्सिंग त्रुटियां परिणामों को जन्म देती हैं। उदाहरण के लिए, यदि आप "खराब" <!DOCTYPE> निर्दिष्ट करते हैं, तो HTML ट्री को QUIRKS के रूप में चिह्नित किया जाएगा और कुछ DOM फ़ंक्शंस के तर्क बदल जाएंगे।

tokenizer

जैसा कि पहले उल्लेख किया गया है, टोकन टोकन यूनिकोड वर्णों को इनपुट के रूप में स्वीकार करता है। यह एक राज्य मशीन है जिसमें 80 राज्य हैं। प्रत्येक राज्य में, यूनिकोड वर्णों के लिए स्थितियाँ। प्राप्त चरित्र के आधार पर, टोकन हो सकता है:

1. अपना राज्य बदलें
2. एक टोकन बनाएं और स्थिति बदलें
3. कुछ मत करो, अगले चरित्र की प्रतीक्षा करो

टोकनधारक छह प्रकार के टोकन बनाता है: DOCTYPE, स्टार्ट टैग, एंड टैग, कमेंट, कैरेक्टर, एंड-टू-फाइल। जो एक पेड़ बनाने के चरण में प्रवेश करते हैं।

यह उल्लेखनीय है कि टोकनधारक को अपने सभी राज्यों के बारे में नहीं पता है, लेकिन जहां लगभग 40% (उदाहरण के लिए, छत से लिया गया है)। "बाकी क्यों?" - आप पूछें। शेष 60% के बारे में एक पेड़ के निर्माण के चरण को जानता है।

यह <textarea> , <style> , <script> , <title> इत्यादि जैसे टैग्स को सही ढंग से पार्स करने के लिए किया जाता है। यही है, आमतौर पर वे टैग जिनमें हम अन्य टैग की उम्मीद नहीं करते हैं, लेकिन केवल खुद को बंद करते हैं।

उदाहरण के लिए, <title> में अन्य टैग नहीं हो सकते। <title> में कोई भी टैग तब तक पाठ के रूप में माना जाएगा जब तक कि वह अपने लिए एक समापन टैग का सामना नहीं करता है </title> ।

ऐसा क्यों किया जाता है? आखिरकार, आप केवल टोकनधारक को बता सकते हैं कि अगर हम <title> पूरा करते हैं <title> तो हम "जिस रास्ते की हमें आवश्यकता है" के साथ जाते हैं। और यह सच होगा अगर नाम स्थान नहीं! हां, नेमस्पेस ट्री-बिल्डिंग चरण के व्यवहार को प्रभावित करता है, जो बदले में टोकन के व्यवहार को बदल देता है।

उदाहरण के रूप में, HTML और SVG नामस्थान में <title> के व्यवहार पर विचार करें:

एचटीएमएल

 <title><span></span></title> 

एक पेड़ के निर्माण का परिणाम:

 <title> "<span></span>" 

एसवीजी

 <svg><title><span></span></title></svg> 

एक पेड़ के निर्माण का परिणाम:

 <svg> <title> <span> "" 

हम देखते हैं कि पहले मामले में (HTML नाम स्थान) <span> पाठ है, span तत्व नहीं बनाया गया था। दूसरे मामले में (SVG नाम स्थान), एक तत्व <span> टैग के आधार पर बनाया गया था। अर्थात्, नामस्थान के आधार पर, टैग अलग-अलग व्यवहार करते हैं।

लेकिन यह सब नहीं है। इस "जीवन का उत्सव" पर केक यह तथ्य है कि टोकनधारक को स्वयं पता होना चाहिए कि पेड़ के निर्माण के चरण को किस नामस्थान में रखा गया है। और CDATA को ठीक से संभालने के लिए यह पूरी तरह से आवश्यक है।

CDATA , दो नामस्थानों के साथ दो उदाहरणों पर विचार करें:

एचटीएमएल

 <div><![CDATA[  ]]></div> 

एक पेड़ के निर्माण का परिणाम:

 <div> <!--[CDATA[  ]]--> 

एसवीजी

 <div><svg><![CDATA[  ]]></svg></div> 

एक पेड़ के निर्माण का परिणाम:

 <div> <svg> "  " 

पहले मामले में (HTML नाम स्थान), टोकन ने टिप्पणी के लिए CDATA लिया। दूसरे मामले में, टोकनधारक ने CDATA संरचना को अलग कर दिया और इससे डेटा प्राप्त किया। सामान्य तौर पर, नियम यह है: यदि हम HTML नामस्थान में CDATA नहीं मिलते हैं, तो हम इसे पार्स करते हैं, अन्यथा हम इसे एक टिप्पणी के रूप में मानते हैं।

यह टोकनर और पेड़ के निर्माण के बीच तंग संबंध है। टोकनधारक को यह पता होना चाहिए कि वर्तमान में ट्री कंस्ट्रक्शन किस चरण में स्थित है, और ट्री कंस्ट्रक्शन का चरण टोकनधारक की स्थिति को बदल सकता है।

टोकन

नीचे हम टोकनधारक द्वारा बनाए गए सभी छह प्रकार के टोकन पर विचार करेंगे। यह ध्यान देने योग्य है कि सभी टोकन ने डेटा तैयार किया है, जो पहले से ही संसाधित है और "उपयोग करने के लिए तैयार है"। इसका मतलब है कि सभी नामित चरित्र संदर्भ, जैसे © , यूनिकोड वर्णों में परिवर्तित हो जाएंगे।

DOCTYPE टोकन

DOCTYPE टोकन की अपनी संरचना अन्य टैग के समान नहीं है। टोकन में शामिल हैं:

1. पहला नाम
2. सार्वजनिक पहचानकर्ता
3. सिस्टम पहचानकर्ता

आधुनिक HTML में, केवल मान्य / मान्य DOCTYPE इस तरह दिखना चाहिए:

 <!DOCTYPE html> 

अन्य सभी <!DOCTYPE> को एक पार्सिंग त्रुटि माना जाएगा।

टैग टोकन प्रारंभ करें

उद्घाटन टैग में हो सकता है:

1. टैग का नाम
2. गुण
3. झंडे

उदाहरण के लिए,

 <div key="value" /> 

उद्घाटन टैग में एक self-closing ध्वज हो सकता है। यह ध्वज टैग के समापन को प्रभावित नहीं करता है, लेकिन गैर- शून्य तत्वों के लिए पार्सिंग त्रुटि का कारण हो सकता है।

अंत टैग टोकन

टैग बंद करना। इसमें शुरुआती टैग के टोकन के सभी गुण हैं, लेकिन टैग नाम के सामने एक स्लैश / है।

 </div key="value" /> 

समापन टैग में एक self-closing ध्वज हो सकता है जो पार्सिंग त्रुटि का कारण होगा। इसके अलावा, पार्सिंग त्रुटि समापन टैग की विशेषताओं के कारण होगी। उन्हें सही ढंग से पार्स किया जाएगा, लेकिन पेड़ के निर्माण के चरण में बाहर फेंक दिया जाएगा।

टिप्पणी टोकन

टिप्पणी टोकन में संपूर्ण टिप्पणी पाठ शामिल है। यही है, यह पूरी तरह से धारा से टोकन की नकल है।

उदाहरण

 <!--  --> 

चरित्र टोकन

शायद सबसे दिलचस्प टोकन। यूनिकोड टोकन प्रतीक। एक (केवल एक) चरित्र हो सकता है।

HTML में प्रत्येक वर्ण के लिए एक टोकन बनाया जाएगा और पेड़ के निर्माण के चरण में भेजा जाएगा। यह बहुत महंगा है।
आइए देखें कि यह कैसे काम करता है।

HTML डेटा लें:

 <span> ! &reg;</span> 

आप क्या सोचते हैं कि इस उदाहरण के लिए कितने टोकन बनाए जाएंगे? उत्तर: 22

निर्मित टोकन की सूची पर विचार करें:

 Start tag token: <span> Character token:  Character token:  Character token:  Character token:  Character token:  Character token: Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token: ! Character token: Character token: End tag token: </span> End-of-file token 

आराम नहीं है, है ना? लेकिन, निश्चित रूप से, HTML पार्सर के कई निर्माता वास्तव में प्रसंस्करण के दौरान केवल एक ही टोकन रखते हैं। इसे एक सर्कल में चलाना और हर बार नए डेटा के साथ इसे ओवरराइट करना।

चलिए आगे बढ़ते हैं और सवाल का जवाब देते हैं: ऐसा क्यों किया जाता है? इस पाठ को एक ही टुकड़े में क्यों नहीं लिया जाए? उत्तर पेड़ के निर्माण के चरण में है।

HTML ट्री बनाने के चरण के बिना एक टोकन बेकार है। यह एक पेड़ बनाने के चरण में है कि पाठ को विभिन्न स्थितियों के साथ एक साथ चिपकाया जाता है।

परिस्थितियाँ निम्नलिखित हैं:

1. यदि U+0000 ( NULL ) के साथ एक वर्ण टोकन आता है, तो हम एक पार्सिंग त्रुटि का कारण बनते हैं और टोकन को अनदेखा करते हैं।
2. यदि कोई U+0009 ( CHARACTER TABULATION ), U+000A ( LINE FEED (LF) ), U+000C ( FORM FEED (FF) ) या U+0020 ( SPACE ) वर्ण टोकन आया है, तो सक्रिय स्वरूपण तत्वों को पुनर्स्थापित करने के लिए एल्गोरिथ्म को कॉल करें और पेड़ में टोकन डालें।

एल्गोरिथ्म के अनुसार पेड़ में प्रतीक टोकन जोड़ा जाता है:

1. यदि वर्तमान सम्मिलन की स्थिति पाठ नोड नहीं है, तो एक पाठ नोड बनाएं, इसे पेड़ में डालें और टोकन से डेटा जोड़ें।
2. अन्यथा, एक मौजूदा पाठ नोड में टोकन से डेटा जोड़ें।

यह व्यवहार बहुत सारी समस्याएं पैदा करता है। प्रत्येक प्रतीक के लिए एक टोकन बनाने और एक पेड़ के निर्माण के चरण के विश्लेषण के लिए भेजने की आवश्यकता है। हम टेक्स्ट नोड के आकार को नहीं जानते हैं और हमें या तो अग्रिम में बहुत सारी मेमोरी आवंटित करनी है या फिर रीक्लोक्स बनाना है। यह सब स्मृति या समय से बहुत महंगा है।

फ़ाइल का अंत टोकन

सरल और स्पष्ट टोकन। डेटा खत्म हो गया है - आइए हम आपको पेड़ निर्माण के इस चरण के बारे में सूचित करते हैं।

एक पेड़ का निर्माण

ट्री बिल्डिंग एक राज्य मशीन है जिसमें 23 राज्य हैं जिनमें टोकन (टैग, टेक्स्ट) की कई शर्तें हैं। एक पेड़ के निर्माण का चरण सबसे बड़ा है, विनिर्देश के एक महत्वपूर्ण हिस्से पर कब्जा कर लेता है, और सुस्त नींद और जलन पैदा करने में भी सक्षम है।

सब कुछ बहुत सरलता से व्यवस्थित है। टोकन इनपुट पर प्राप्त होते हैं और, टोकन के आधार पर, पेड़ के निर्माण की स्थिति बदल जाती है। आउटपुट पर, हमारे पास एक वास्तविक DOM है।

कोई समस्या?

निम्नलिखित समस्याएं काफी स्पष्ट लगती हैं:

चरित्र-दर-चरित्र नकल

प्रत्येक टोकेनाइज़र राज्य इनपुट पर एक वर्ण प्राप्त करता है, जिसे यह आवश्यक होने पर कॉपी / परिवर्तित करता है: टैग नाम, गुण, टिप्पणी, प्रतीक।

यह स्मृति और समय दोनों में बहुत बेकार है। हमें प्रत्येक विशेषता, टैग नाम, टिप्पणी और इसी तरह की स्मृति के लिए अज्ञात मात्रा में प्रचार करने के लिए मजबूर किया जाता है। और यह, तदनुसार, पुनःप्रकाश की ओर जाता है, और पुनःप्रकाश खोए हुए समय को जन्म देता है।

और यदि आप कल्पना करते हैं कि HTML में 1000 टैग हैं, और प्रत्येक टैग में कम से कम एक विशेषता है, तो हमें एक नारकीय धीमा पार्सर मिलता है।

चरित्र टोकन

दूसरी समस्या चरित्र टोकन है। यह पता चला है कि हम प्रत्येक प्रतीक के लिए एक टोकन बनाते हैं और इसे एक पेड़ बनाने के लिए देते हैं। एक पेड़ का निर्माण यह नहीं जानता कि इनमें से कितने टोकन हमारे पास होंगे और पात्रों की आवश्यक संख्या के लिए स्मृति को तुरंत आवंटित नहीं कर सकते हैं। तदनुसार, यहां पेड़ की वर्तमान स्थिति में एक पाठ नोड की उपस्थिति के लिए सभी समान रीप्लेक्स + निरंतर जांच।

अखंड प्रणाली

बड़ी समस्या हर चीज पर निर्भरता की है। यही है, टोकनधारक पेड़ के निर्माण की स्थिति पर निर्भर करता है, और पेड़ का निर्माण टोकनधारक को नियंत्रित कर सकता है। और सब कुछ नामस्थान (नामस्थान) के लिए दोषी है।

हम समस्याओं का समाधान कैसे करेंगे?

आगे, मैं अपने लेक्सबोर प्रोजेक्ट में HTML पार्सर के कार्यान्वयन के साथ-साथ सभी समस्याओं के समाधान का वर्णन करूंगा।

पूर्व उपचार

हम प्रारंभिक डेटा प्रोसेसिंग को हटा देते हैं। हम एक टोकन को अंतरिक्ष चरित्र के रूप में कैरिज रिटर्न ( \r ) को समझने के लिए प्रशिक्षित करेंगे। इस प्रकार, वह एक पेड़ बनाने के चरण में फेंक दिया जाएगा जहां हम इसका पता लगाएंगे।

टोकन

कलाई की एक झिलमिलाहट के साथ हम सभी टोकन को एकजुट करते हैं। हमारे पास हर चीज के लिए एक टोकन होगा। सामान्य तौर पर, पूरी पार्सिंग प्रक्रिया में केवल एक ही टोकन होगा।

हमारे एकीकृत टोकन में निम्नलिखित फ़ील्ड शामिल होंगे:

1. टैग आईडी
2. शुरू करना
3. अंत
4. गुण
5. झंडे

टैग आईडी

हम टैग नाम के शाब्दिक प्रतिनिधित्व के साथ काम नहीं करेंगे। हम सब कुछ संख्याओं में अनुवाद करते हैं। संख्या की तुलना करना आसान है, साथ काम करना आसान है।

हम सभी ज्ञात टैग से एक स्थिर हैश तालिका बनाते हैं। हम सभी ज्ञात टैग से एनम बनाते हैं। यही है, हमें प्रत्येक टैग को एक पहचानकर्ता को सख्ती से असाइन करने की आवश्यकता है। तदनुसार, हैश तालिका में, कुंजी टैग का नाम है, और मान गणना से लिखा गया है।

एक उदाहरण के लिए:

 typedef enum { LXB_TAG__UNDEF = 0x0000, LXB_TAG__END_OF_FILE = 0x0001, LXB_TAG__TEXT = 0x0002, LXB_TAG__DOCUMENT = 0x0003, LXB_TAG__EM_COMMENT = 0x0004, LXB_TAG__EM_DOCTYPE = 0x0005, LXB_TAG_A = 0x0006, LXB_TAG_ABBR = 0x0007, LXB_TAG_ACRONYM = 0x0008, LXB_TAG_ADDRESS = 0x0009, LXB_TAG_ALTGLYPH = 0x000a, /* ... */ } 

जैसा कि आप उदाहरण से देख सकते हैं, हमने एक दस्तावेज़ के लिए, पाठ के लिए END-OF-FILE टोकन के लिए टैग बनाए। यह सब आगे की सुविधा के लिए। पर्दा खोलते हुए, मैं कहूंगा कि नोड ( DOM Node Interface ) में हमारे पास एक Tag ID । यह दो तुलना करने के लिए नहीं किया जाता है: नोड के प्रकार और तत्व पर। यही है, अगर हमें DIV तत्व की आवश्यकता है, तो हम नोड में एक चेक करते हैं:

 if (node->tag_id == LXB_TAG_DIV) { /* Best code */ } 

लेकिन, निश्चित रूप से, आप यह कर सकते हैं:

 if (node->type == LXB_DOM_NODE_TYPE_ELEMENT && node->tag_id == LXB_TAG_DIV) { /* Oh, code */ } 

LXB_TAG__ में दो अंडरस्कोर को सामान्य टैग को सिस्टम से अलग करने की आवश्यकता है। दूसरे शब्दों में, उपयोगकर्ता नाम text या end-of-file साथ एक टैग बना सकता है end-of-file और यदि हम फिर टैग नाम से खोज करते हैं, तो कोई त्रुटि नहीं होगी। सभी सिस्टम टैग एक # शुरू होते हैं।

लेकिन फिर भी, एक नोड टैग नाम के पाठ प्रतिनिधित्व को संग्रहीत कर सकता है। 98.99999% नोड्स के लिए, यह पैरामीटर NULL होगा। कुछ नामस्थानों में, हमें एक निश्चित रजिस्टर के साथ एक उपसर्ग या टैग नाम निर्दिष्ट करना होगा। उदाहरण के लिए, एसवीजी नामस्थान में baseProfile ।

कार्य का तर्क सरल है। अगर हमारे पास स्पष्ट रूप से परिभाषित रजिस्टर के साथ एक टैग है:

1. इसे लोअर केस में टैग के सामान्य आधार में जोड़ें। टैग आईडी प्राप्त करें।
2. नोड के लिए पाठ प्रतिनिधित्व में टैग पहचानकर्ता और मूल टैग नाम जोड़ें।

कस्टम टैग

एक डेवलपर HTML में कोई भी टैग बना सकता है। चूंकि हमारे पास केवल वे टैग हैं जिनके बारे में हम एक स्थिर हैश तालिका में जानते हैं, और उपयोगकर्ता कोई भी बना सकता है, हमें एक गतिशील हैश तालिका की आवश्यकता है।

सब कुछ बहुत सरल दिखता है। जब टैग हमारे पास आता है, तो हम देखेंगे कि क्या यह स्थिर हैश तालिका में है। यदि कोई टैग नहीं है, तो आइए डायनामिक में देखें, यदि वहाँ नहीं है, तो हम एक से पहचानकर्ता काउंटर बढ़ाते हैं और डायनामिक तालिका में टैग जोड़ते हैं।

वर्णित सब कुछ टोकन के चरण में होता है। टोकन के अंदर और सभी तुलनाओं के बाद Tag ID (दुर्लभ अपवादों के साथ) पर जाएं।

शुरू और अंत

अब टोकनधारक में हमारे पास डाटा प्रोसेसिंग नहीं होगी। हम कुछ भी कॉपी और कन्वर्ट नहीं करेंगे। हम डेटा की शुरुआत और अंत में सिर्फ पॉइंटर्स लेते हैं।

सभी डेटा प्रोसेसिंग, जैसे प्रतीकात्मक लिंक, ट्री-बिल्डिंग चरण में होंगे।
इस प्रकार, हम मेमोरी के बाद के आवंटन के लिए डेटा के आकार को जान पाएंगे।

गुण

यहाँ सब कुछ उतना ही सरल है। हम कुछ भी कॉपी नहीं करते हैं, लेकिन केवल नाम और विशेषता मानों की शुरुआत / अंत में संकेत बचाते हैं। पेड़ बनने के समय सभी परिवर्तन होते हैं।

झंडे

चूंकि हमने टोकन को एकजुट किया है, इसलिए हमें किसी तरह से पेड़ के निर्माण को टोकन के प्रकार के बारे में सूचित करना होगा। ऐसा करने के लिए, फ्लैगस बिटमैप फ़ील्ड का उपयोग करें।

फ़ील्ड में निम्न मान हो सकते हैं:

 enum { LXB_HTML_TOKEN_TYPE_OPEN = 0x0000, LXB_HTML_TOKEN_TYPE_CLOSE = 0x0001, LXB_HTML_TOKEN_TYPE_CLOSE_SELF = 0x0002, LXB_HTML_TOKEN_TYPE_TEXT = 0x0004, LXB_HTML_TOKEN_TYPE_DATA = 0x0008, LXB_HTML_TOKEN_TYPE_RCDATA = 0x0010, LXB_HTML_TOKEN_TYPE_CDATA = 0x0020, LXB_HTML_TOKEN_TYPE_NULL = 0x0040, LXB_HTML_TOKEN_TYPE_FORCE_QUIRKS = 0x0080, LXB_HTML_TOKEN_TYPE_DONE = 0x0100 }; 

टोकन खोलने या बंद करने के प्रकार के अलावा, डेटा कनवर्टर के लिए मान हैं। केवल टोकनधारक जानता है कि डेटा को सही तरीके से कैसे परिवर्तित किया जाए। तदनुसार, टोकन के टोकन से पता चलता है कि डेटा को कैसे संसाधित किया जाना चाहिए।

चरित्र टोकन

पहले वर्णित से, हम यह निष्कर्ष निकाल सकते हैं कि प्रतीक टोकन हमसे गायब हो गया है। हां, अब हमारे पास एक नए प्रकार का टोकन है: LXB_HTML_TOKEN_TYPE_TEXT । अब हम टैग के बीच पूरे पाठ के लिए एक टोकन बनाते हैं, यह चिह्नित करते हुए कि इसे भविष्य में कैसे संसाधित किया जाना चाहिए।

इस वजह से, हमें पेड़ के निर्माण में शर्तों को बदलना होगा। हमें उसे प्रतीकात्मक टोकन के साथ काम करने के लिए प्रशिक्षित करने की आवश्यकता है, लेकिन पाठ टोकन के साथ: कन्वर्ट, अनावश्यक वर्णों को हटा दें, रिक्त स्थान को छोड़ दें और इसी तरह।

लेकिन, कुछ भी जटिल नहीं है। एक पेड़ बनाने के चरण में, परिवर्तन न्यूनतम होंगे। लेकिन टोकन अब शब्द से विनिर्देश से मेल नहीं खाता है। लेकिन हमें उसकी जरूरत नहीं है, यह सामान्य है। हमारा कार्य HTML / DOM ट्री प्राप्त करना है जो विशिष्टताओं का पूरी तरह पालन करता है।

टोकन धारक

टोकन में उच्च गति डेटा प्रसंस्करण सुनिश्चित करने के लिए, हम प्रत्येक चरण में अपने पुनरावृत्ति को जोड़ेंगे। विनिर्देश के अनुसार, प्रत्येक चरण हमारे लिए एक प्रतीक स्वीकार करता है और, जो प्रतीक आया है, उसके आधार पर निर्णय लेता है। लेकिन, सच्चाई यह है कि यह बहुत महंगा है।

उदाहरण के लिए, ATTRIBUTE_NAME चरण से ATTRIBUTE_NAME चरण में जाने के लिए ATTRIBUTE_VALUE हमें विशेषता नाम में एक सफेद स्थान ढूंढना होगा, जो इसके अंत का संकेत देगा। विनिर्देश के अनुसार, हमें व्हाट्सएप चरित्र ATTRIBUTE_NAME तक ATTRIBUTE_NAME के चरण में चरित्र द्वारा फ़ीड करना चाहिए, और यह चरण किसी अन्य पर स्विच नहीं करता है। यह बहुत महंगा है, आमतौर पर इसे प्रत्येक वर्ण या कॉलबैक जैसे "t search> next_code_point ()" के लिए फ़ंक्शन कॉल के माध्यम से कार्यान्वित किया जाता है।

हम ATTRIBUTE_NAME चरण में एक लूप जोड़ते हैं और पूरे आने वाले बफर को पास करते हैं। लूप में, हम उन प्रतीकों की तलाश करते हैं जिन्हें हमें स्विच करने और अगले चरण पर काम करना जारी रखना चाहिए। यहां हमें बहुत सी जीत मिलती है, यहां तक ​​कि संकलक अनुकूलन भी।

लेकिन! सबसे बुरी बात यह है कि हमने बॉक्स से बाहर चूजों (चूजों) का समर्थन तोड़ दिया। टोकनर के प्रत्येक चरण में चरित्र-दर-प्रतीक प्रसंस्करण के लिए धन्यवाद, हमारे पास चंक्स के लिए समर्थन था, और अब हमने इसे तोड़ दिया है।

इसे कैसे ठीक करें? विखंडू के लिए समर्थन कैसे लागू करें?! यह सरल है, हम आने वाले बफ़र्स (आने वाले बफ़र) की अवधारणा को पेश करते हैं।

आने वाला बफर

अक्सर HTML chunks में parses। उदाहरण के लिए, यदि हम नेटवर्क पर डेटा प्राप्त करते हैं। शेष डेटा की प्रतीक्षा करते समय बेकार नहीं खड़े होने के लिए, हम पहले से ही प्राप्त डेटा को प्रसंस्करण / पार्सिंग के लिए भेज सकते हैं। स्वाभाविक रूप से, डेटा कहीं भी फाड़ा जा सकता है। उदाहरण के लिए, हमारे पास दो बफ़र हैं:

पहले

 <div clas 

दूसरा

 s="oh-no-oh-no"> 

चूंकि हम टोकन चरण में कुछ भी कॉपी नहीं करते हैं, लेकिन केवल डेटा की शुरुआत और अंत में संकेत लेते हैं, हमारे पास एक समस्या है। विभिन्न उपयोगकर्ता बफ़र्स को इंगित करता है। , .

.
:

1. (Incoming Buffer).
2. ( ) , ? , . , . 99% .

" " . .

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

:

, . , : . . ( ), . .

: . , .

.

, . , .

:

 tree_build_in_body_character(token) { if (token.code_point == '\0') { /* Parse error, ignore token */ } else if (token.code_point == whitespaces) { /* Insert element */' } /* ... */ } 

Lexbor HTML

 tree_build_in_body_character(token) { lexbor_str_t str = {0}; lxb_html_parser_char_t pc = {0}; pc.drop_null = true; tree->status = lxb_html_token_parse_data(token, &pc, &str, tree->document->mem->text); if (token->type & LXB_HTML_TOKEN_TYPE_NULL) { /* Parse error */ } /* Insert element if not empty */ } 

, . :

 pc.replace_null /*   '\0'    (REPLACEMENT CHARACTER (U+FFFD)) */ pc.drop_null /*   '\0' */ pc.is_attribute /*          " " */ pc.state /*  .        . */ 

. - \0 , - REPLACEMENT CHARACTER . - , - . .

, . . , <head> . , , : " ". , .

 An end tag whose tag name is "sarcasm" Take a deep breath, then act as described in the "any other end tag" entry below. 

HTML DOM/HTML Interfaces HTML/DOM HTML .

, :

1. ( )
2. 
   
   • Incoming Buffer
   • Tag ID
   • ̆ : , N+
   • ̆
   • ̈
3. 
   

i7 2012 , , 235MB (Amazon-).

, 1.5/2 , . , . , CSS (Grammar, , Grammar). HTML, CSS , "".

स्रोत कोड

HTML Lexbor HTML .

पुनश्च

CSS Grammar. , . - 6-8 .

आपका ध्यान के लिए धन्यवाद!