layout: Add initial support for bidirectional text (BiDi) (#33148)

This adds supports for right-to-left text assigning bidi levels to all
line items when necessary. This includes support for the `dir` attribute
as well as corresponding CSS properties like `unicode-bidi`. It only
implements right-to-left rendering for inline layout at the moment and
doesn't include support for `dir=auto`. Because of missing features,
this causes quite a few tests to start failing, as references become
incorrect due to right-to-left rendering being active in some cases,
but not others (before it didn't exist at all).

Analysis of most of the new failures:

```
- /css/css-flexbox/gap-001-rtl.html
  /css/css-flexbox/gap-004-rtl.html
 - Require implementing BiDi in Flexbox, because the start and
   end inline margins are opposite the order of items.

- /css/CSS2/bidi-text/direction-applies-to-*.xht
  /css/CSS2/bidi-text/direction-applies-to-002.xht
  /css/CSS2/bidi-text/direction-applies-to-003.xht
  /css/CSS2/bidi-text/direction-applies-to-004.xht
  - Broken due to a bug in tables, not allocating the
    right amount of width for a column.

- /css/css-lists/inline-list.html
  - This fails because we wrongly insert a soft wrap opportunity between the
    start of an inline box and its first content.

- /css/css-text/bidi/bidi-lines-001.html
  /css/css-text/bidi/bidi-lines-002.html
  /css/CSS2/text/bidi-flag-emoji.html
  - We do not fully support unicode-bidi: plaintext

- /css/css-text/text-align/text-align-end-010.html
  /css/css-text/text-align/text-align-justify-006.html
  /css/css-text/text-align/text-align-start-010.html
  /html/dom/elements/global-attributes/*
  - We do not support dir=auto yet.

- /css/css-text/white-space/tab-bidi-001.html
  - Servo doesn't support tab stops

- /css/CSS2/positioning/abspos-block-level-001.html
  /css/css-text/word-break/word-break-normal-ar-000.html
  - Do not yet support RTL layout in block

- /css/css-text/white-space/pre-wrap-018.html
  - Even in RTL contexts, spaces at the end of the line must hang and
    not be reordered

- /css/css-text/white-space/trailing-space-and-text-alignment-rtl-002.html
  - We are letting spaces hang with white-space: pre, but they shouldn't
    hang.
```

Signed-off-by: Martin Robinson <mrobinson@igalia.com>
Co-authored-by: Rakhi Sharma <atbrakhi@igalia.com>

6 files changed, 215 insertions, 84 deletions

diff --git a/components/layout_2020/flow/construct.rs b/components/layout_2020/flow/construct.rs
index c52790d6348..7695383b00c 100644
--- a/components/layout_2020/flow/construct.rs
+++ b/components/layout_2020/flow/construct.rs
@@ -217,6 +217,7 @@ where
             self.text_decoration_line,
             !self.have_already_seen_first_line_for_text_indent,
             self.info.is_single_line_text_input(),
+            self.info.style.writing_mode.to_bidi_level(),
         ) {
             // There are two options here. This block was composed of both one or more inline formatting contexts
             // and child blocks OR this block was a single inline formatting context. In the latter case, we
@@ -489,6 +490,7 @@ where
                 self.context,
                 self.text_decoration_line,
                 !self.have_already_seen_first_line_for_text_indent,
+                self.info.style.writing_mode.to_bidi_level(),
             )
         {
             self.push_block_level_job_for_inline_formatting_context(inline_formatting_context);
@@ -602,6 +604,7 @@ where
             self.text_decoration_line,
             !self.have_already_seen_first_line_for_text_indent,
             self.info.is_single_line_text_input(),
+            self.info.style.writing_mode.to_bidi_level(),
         ) {
             self.push_block_level_job_for_inline_formatting_context(inline_formatting_context);
         }
diff --git a/components/layout_2020/flow/inline/construct.rs b/components/layout_2020/flow/inline/construct.rs
index c6b224f8708..ecce2e5f8e4 100644
--- a/components/layout_2020/flow/inline/construct.rs
+++ b/components/layout_2020/flow/inline/construct.rs
@@ -8,6 +8,7 @@ use std::char::{ToLowercase, ToUppercase};
 use style::computed_values::white_space_collapse::T as WhiteSpaceCollapse;
 use style::values::computed::TextDecorationLine;
 use style::values::specified::text::TextTransformCase;
+use unicode_bidi::Level;
 use unicode_segmentation::UnicodeSegmentation;
 
 use super::text_run::TextRun;
@@ -19,6 +20,7 @@ use crate::dom_traversal::NodeAndStyleInfo;
 use crate::flow::float::FloatBox;
 use crate::formatting_contexts::IndependentFormattingContext;
 use crate::positioned::AbsolutelyPositionedBox;
+use crate::style_ext::ComputedValuesExt;
 
 #[derive(Default)]
 pub(crate) struct InlineFormattingContextBuilder {
@@ -82,6 +84,11 @@ impl InlineFormattingContextBuilder {
         !self.inline_box_stack.is_empty()
     }
 
+    fn push_control_character_string(&mut self, string_to_push: &str) {
+        self.text_segments.push(string_to_push.to_owned());
+        self.current_text_offset += string_to_push.len();
+    }
+
     /// Return true if this [`InlineFormattingContextBuilder`] is empty for the purposes of ignoring
     /// during box tree construction. An IFC is empty if it only contains TextRuns with
     /// completely collapsible whitespace. When that happens it can be ignored completely.
@@ -101,7 +108,7 @@ impl InlineFormattingContextBuilder {
                 // Text content is handled by `self.has_uncollapsible_text` content above in order
                 // to avoid having to iterate through the character once again.
                 InlineItem::TextRun(_) => true,
-                InlineItem::OutOfFlowAbsolutelyPositionedBox(_) => false,
+                InlineItem::OutOfFlowAbsolutelyPositionedBox(..) => false,
                 InlineItem::OutOfFlowFloatBox(_) => false,
                 InlineItem::Atomic(..) => false,
             }
@@ -119,14 +126,13 @@ impl InlineFormattingContextBuilder {
         let inline_level_box = ArcRefCell::new(InlineItem::Atomic(
             independent_formatting_context,
             self.current_text_offset,
+            Level::ltr(), /* This will be assigned later if necessary. */
         ));
         self.inline_items.push(inline_level_box.clone());
 
         // Push an object replacement character for this atomic, which will ensure that the line breaker
         // inserts a line breaking opportunity here.
-        let string_to_push = "\u{fffc}";
-        self.text_segments.push(string_to_push.to_owned());
-        self.current_text_offset += string_to_push.len();
+        self.push_control_character_string("\u{fffc}");
 
         self.last_inline_box_ended_with_collapsible_white_space = false;
         self.on_word_boundary = true;
@@ -141,7 +147,9 @@ impl InlineFormattingContextBuilder {
         let absolutely_positioned_box = ArcRefCell::new(absolutely_positioned_box);
         let inline_level_box = ArcRefCell::new(InlineItem::OutOfFlowAbsolutelyPositionedBox(
             absolutely_positioned_box,
+            self.current_text_offset,
         ));
+
         self.inline_items.push(inline_level_box.clone());
         inline_level_box
     }
@@ -154,6 +162,8 @@ impl InlineFormattingContextBuilder {
     }
 
     pub(crate) fn start_inline_box(&mut self, inline_box: InlineBox) {
+        self.push_control_character_string(inline_box.style.bidi_control_chars().0);
+
         let identifier = self.inline_boxes.start_inline_box(inline_box);
         self.inline_items
             .push(ArcRefCell::new(InlineItem::StartInlineBox(identifier)));
@@ -164,6 +174,9 @@ impl InlineFormattingContextBuilder {
         let identifier = self.end_inline_box_internal();
         let inline_level_box = self.inline_boxes.get(&identifier);
         inline_level_box.borrow_mut().is_last_fragment = true;
+
+        self.push_control_character_string(inline_level_box.borrow().style.bidi_control_chars().1);
+
         inline_level_box
     }
 
@@ -261,6 +274,7 @@ impl InlineFormattingContextBuilder {
         layout_context: &LayoutContext,
         text_decoration_line: TextDecorationLine,
         has_first_formatted_line: bool,
+        default_bidi_level: Level,
     ) -> Option<InlineFormattingContext> {
         if self.is_empty() {
             return None;
@@ -293,6 +307,7 @@ impl InlineFormattingContextBuilder {
             text_decoration_line,
             has_first_formatted_line,
             /* is_single_line_text_input = */ false,
+            default_bidi_level,
         )
     }
 
@@ -303,6 +318,7 @@ impl InlineFormattingContextBuilder {
         text_decoration_line: TextDecorationLine,
         has_first_formatted_line: bool,
         is_single_line_text_input: bool,
+        default_bidi_level: Level,
     ) -> Option<InlineFormattingContext> {
         if self.is_empty() {
             return None;
@@ -317,6 +333,7 @@ impl InlineFormattingContextBuilder {
             text_decoration_line,
             has_first_formatted_line,
             is_single_line_text_input,
+            default_bidi_level,
         ))
     }
 }
diff --git a/components/layout_2020/flow/inline/line.rs b/components/layout_2020/flow/inline/line.rs
index 22f52439bd2..68095c0f8c3 100644
--- a/components/layout_2020/flow/inline/line.rs
+++ b/components/layout_2020/flow/inline/line.rs
@@ -3,7 +3,6 @@
  * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
 
 use std::rc::Rc;
-use std::vec::IntoIter;
 
 use app_units::Au;
 use bitflags::bitflags;
@@ -18,6 +17,7 @@ use style::values::specified::box_::DisplayOutside;
 use style::values::specified::text::TextDecorationLine;
 use style::values::Either;
 use style::Zero;
+use unicode_bidi::{BidiInfo, Level};
 use webrender_api::FontInstanceKey;
 
 use super::inline_box::{
@@ -170,7 +170,7 @@ pub(super) struct LineItemLayout<'a> {
 impl<'a> LineItemLayout<'a> {
     pub(super) fn layout_line_items(
         state: &mut InlineFormattingContextState,
-        iterator: &mut IntoIter<LineItem>,
+        line_items: Vec<LineItem>,
         start_position: LogicalVec2<Au>,
         effective_block_advance: &LineBlockSizes,
         justification_adjustment: Au,
@@ -191,7 +191,7 @@ impl<'a> LineItemLayout<'a> {
             },
             justification_adjustment,
         }
-        .layout(iterator)
+        .layout(line_items, state.has_right_to_left_content)
     }
 
     /// Start and end inline boxes in tree order, so that it reflects the given inline box.
@@ -217,8 +217,40 @@ impl<'a> LineItemLayout<'a> {
         }
     }
 
-    pub(super) fn layout(&mut self, iterator: &mut IntoIter<LineItem>) -> Vec<Fragment> {
-        for item in iterator.by_ref() {
+    pub(super) fn layout(
+        &mut self,
+        mut line_items: Vec<LineItem>,
+        has_right_to_left_content: bool,
+    ) -> Vec<Fragment> {
+        let mut last_level: Level = Level::ltr();
+        let levels: Vec<_> = line_items
+            .iter()
+            .map(|item| {
+                let level = match item {
+                    LineItem::TextRun(_, text_run) => text_run.bidi_level,
+                    // TODO: This level needs either to be last_level, or if there were
+                    // unicode characters inserted for the inline box, we need to get the
+                    // level from them.
+                    LineItem::StartInlineBoxPaddingBorderMargin(_) => last_level,
+                    LineItem::EndInlineBoxPaddingBorderMargin(_) => last_level,
+                    LineItem::Atomic(_, atomic) => atomic.bidi_level,
+                    LineItem::AbsolutelyPositioned(..) => last_level,
+                    LineItem::Float(..) => {
+                        // At this point the float is already positioned, so it doesn't really matter what
+                        // position it's fragment has in the order of line items.
+                        last_level
+                    },
+                };
+                last_level = level;
+                level
+            })
+            .collect();
+
+        if has_right_to_left_content {
+            sort_by_indices_in_place(&mut line_items, BidiInfo::reorder_visual(&levels));
+        }
+
+        for item in line_items.into_iter().by_ref() {
             // When preparing to lay out a new line item, start and end inline boxes, so that the current
             // inline box state reflects the item's parent. Items in the line are not necessarily in tree
             // order due to BiDi and other reordering so the inline box of the item could potentially be
@@ -304,10 +336,10 @@ impl<'a> LineItemLayout<'a> {
     }
 
     fn end_inline_box(&mut self) {
-        let outer_state = self.state_stack.pop().expect("Ended unknown inline box 11");
+        let outer_state = self.state_stack.pop().expect("Ended unknown inline box");
         let mut inner_state = std::mem::replace(&mut self.state, outer_state);
 
-        let identifier = inner_state.identifier.expect("Ended unknown inline box 22");
+        let identifier = inner_state.identifier.expect("Ended unknown inline box");
         let inline_box_state = &*self.inline_box_states[identifier.index_in_inline_boxes as usize];
         let inline_box = self.inline_boxes.get(&identifier);
         let inline_box = &*(inline_box.borrow());
@@ -315,23 +347,24 @@ impl<'a> LineItemLayout<'a> {
         let mut padding = inline_box_state.pbm.padding;
         let mut border = inline_box_state.pbm.border;
         let mut margin = inline_box_state.pbm.margin.auto_is(Au::zero);
-        if !inner_state
+
+        let had_start = inner_state
             .flags
-            .contains(LineLayoutInlineContainerFlags::HAD_START_PBM)
-        {
+            .contains(LineLayoutInlineContainerFlags::HAD_START_PBM);
+        let had_end = inner_state
+            .flags
+            .contains(LineLayoutInlineContainerFlags::HAD_END_PBM);
+
+        if !had_start {
             padding.inline_start = Au::zero();
             border.inline_start = Au::zero();
             margin.inline_start = Au::zero();
         }
-        if !inner_state
-            .flags
-            .contains(LineLayoutInlineContainerFlags::HAD_END_PBM)
-        {
+        if !had_end {
             padding.inline_end = Au::zero();
             border.inline_end = Au::zero();
             margin.inline_end = Au::zero();
         }
-
         // If the inline box didn't have any content at all and it isn't the first fragment for
         // an element (needed for layout queries currently) and it didn't have any padding, border,
         // or margin do not make a fragment for it.
@@ -339,12 +372,7 @@ impl<'a> LineItemLayout<'a> {
         // Note: This is an optimization, but also has side effects. Any fragments on a line will
         // force the baseline to advance in the parent IFC.
         let pbm_sums = padding + border + margin;
-        if inner_state.fragments.is_empty() &&
-            !inner_state
-                .flags
-                .contains(LineLayoutInlineContainerFlags::HAD_START_PBM) &&
-            pbm_sums.inline_sum().is_zero()
-        {
+        if inner_state.fragments.is_empty() && !had_start && pbm_sums.inline_sum().is_zero() {
             return;
         }
 
@@ -645,6 +673,8 @@ pub(super) struct TextRunLineItem {
     pub font_metrics: FontMetrics,
     pub font_key: FontInstanceKey,
     pub text_decoration_line: TextDecorationLine,
+    /// The BiDi level of this [`TextRunLineItem`] to enable reordering.
+    pub bidi_level: Level,
 }
 
 impl TextRunLineItem {
@@ -697,6 +727,10 @@ impl TextRunLineItem {
         // Only keep going if we only encountered whitespace.
         self.text.is_empty()
     }
+
+    pub(crate) fn can_merge(&self, font_key: FontInstanceKey, bidi_level: Level) -> bool {
+        self.font_key == font_key && self.bidi_level == bidi_level
+    }
 }
 
 pub(super) struct AtomicLineItem {
@@ -711,6 +745,9 @@ pub(super) struct AtomicLineItem {
 
     /// The offset of the baseline inside this item.
     pub baseline_offset_in_item: Au,
+
+    /// The BiDi level of this [`AtomicLineItem`] to enable reordering.
+    pub bidi_level: Level,
 }
 
 impl AtomicLineItem {
@@ -753,3 +790,24 @@ fn line_height(parent_style: &ComputedValues, font_metrics: &FontMetrics) -> Len
         LineHeight::Length(length) => length.0,
     }
 }
+
+/// Sort a mutable slice by the the given indices array in place, reording the slice so that final
+/// value of `slice[x]` is `slice[indices[x]]`.
+fn sort_by_indices_in_place<T>(data: &mut [T], mut indices: Vec<usize>) {
+    for idx in 0..data.len() {
+        if indices[idx] == idx {
+            continue;
+        }
+
+        let mut current_idx = idx;
+        loop {
+            let target_idx = indices[current_idx];
+            indices[current_idx] = current_idx;
+            if indices[target_idx] == target_idx {
+                break;
+            }
+            data.swap(current_idx, target_idx);
+            current_idx = target_idx;
+        }
+    }
+}
diff --git a/components/layout_2020/flow/inline/mod.rs b/components/layout_2020/flow/inline/mod.rs
index bf20802dbbb..22632cee22f 100644
--- a/components/layout_2020/flow/inline/mod.rs
+++ b/components/layout_2020/flow/inline/mod.rs
@@ -108,6 +108,7 @@ use text_run::{
     add_or_get_font, get_font_for_first_font_for_style, TextRun, XI_LINE_BREAKING_CLASS_GL,
     XI_LINE_BREAKING_CLASS_WJ, XI_LINE_BREAKING_CLASS_ZWJ,
 };
+use unicode_bidi::{BidiInfo, Level};
 use webrender_api::FontInstanceKey;
 use xi_unicode::linebreak_property;
 
@@ -161,8 +162,12 @@ pub(crate) struct InlineFormattingContext {
     /// Whether or not this [`InlineFormattingContext`] contains floats.
     pub(super) contains_floats: bool,
 
-    /// Whether or not this is an inline formatting context for a single line text input.
+    /// Whether or not this is an [`InlineFormattingContext`] for a single line text input.
     pub(super) is_single_line_text_input: bool,
+
+    /// Whether or not this is an [`InlineFormattingContext`] has right-to-left content, which
+    /// will require reordering during layout.
+    pub(super) has_right_to_left_content: bool,
 }
 
 /// A collection of data used to cache [`FontMetrics`] in the [`InlineFormattingContext`]
@@ -178,11 +183,15 @@ pub(crate) enum InlineItem {
     StartInlineBox(InlineBoxIdentifier),
     EndInlineBox,
     TextRun(TextRun),
-    OutOfFlowAbsolutelyPositionedBox(ArcRefCell<AbsolutelyPositionedBox>),
+    OutOfFlowAbsolutelyPositionedBox(
+        ArcRefCell<AbsolutelyPositionedBox>,
+        usize, /* offset_in_text */
+    ),
     OutOfFlowFloatBox(FloatBox),
     Atomic(
         IndependentFormattingContext,
         usize, /* offset_in_text */
+        Level, /* bidi_level */
     ),
 }
 
@@ -639,6 +648,9 @@ pub(super) struct InlineFormattingContextState<'a, 'b> {
     /// are laying out. This is used to propagate baselines to the ancestors of
     /// `display: inline-block` elements and table content.
     baselines: Baselines,
+
+    /// Whether or not the [`InlineFormattingContext`] being laid out has right-to-left content.
+    has_right_to_left_content: bool,
 }
 
 impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
@@ -853,7 +865,7 @@ impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
         let start_positioning_context_length = self.positioning_context.len();
         let fragments = LineItemLayout::layout_line_items(
             self,
-            &mut line_to_layout.line_items.into_iter(),
+            line_to_layout.line_items,
             start_position,
             &effective_block_advance,
             justification_adjustment,
@@ -907,9 +919,9 @@ impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
         last_line_or_forced_line_break: bool,
     ) -> (Au, Au) {
         enum TextAlign {
-            Start,
+            Left,
             Center,
-            End,
+            Right,
         }
         let style = self.containing_block.style;
         let mut text_align_keyword = style.clone_text_align();
@@ -930,24 +942,24 @@ impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
         }
 
         let text_align = match text_align_keyword {
-            TextAlignKeyword::Start => TextAlign::Start,
-            TextAlignKeyword::Center | TextAlignKeyword::MozCenter => TextAlign::Center,
-            TextAlignKeyword::End => TextAlign::End,
-            TextAlignKeyword::Left | TextAlignKeyword::MozLeft => {
-                if style.effective_writing_mode().line_left_is_inline_start() {
-                    TextAlign::Start
+            TextAlignKeyword::Start => {
+                if style.writing_mode.line_left_is_inline_start() {
+                    TextAlign::Left
                 } else {
-                    TextAlign::End
+                    TextAlign::Right
                 }
             },
-            TextAlignKeyword::Right | TextAlignKeyword::MozRight => {
-                if style.effective_writing_mode().line_left_is_inline_start() {
-                    TextAlign::End
+            TextAlignKeyword::Center | TextAlignKeyword::MozCenter => TextAlign::Center,
+            TextAlignKeyword::End => {
+                if style.writing_mode.line_left_is_inline_start() {
+                    TextAlign::Right
                 } else {
-                    TextAlign::Start
+                    TextAlign::Left
                 }
             },
-            TextAlignKeyword::Justify => TextAlign::Start,
+            TextAlignKeyword::Left | TextAlignKeyword::MozLeft => TextAlign::Left,
+            TextAlignKeyword::Right | TextAlignKeyword::MozRight => TextAlign::Right,
+            TextAlignKeyword::Justify => TextAlign::Left,
         };
 
         let (line_start, available_space) = match self.current_line.placement_among_floats.get() {
@@ -968,8 +980,8 @@ impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
         let line_length = self.current_line.inline_position - whitespace_trimmed - text_indent;
         let adjusted_line_start = line_start +
             match text_align {
-                TextAlign::Start => text_indent,
-                TextAlign::End => (available_space - line_length).max(text_indent),
+                TextAlign::Left => text_indent,
+                TextAlign::Right => (available_space - line_length).max(text_indent),
                 TextAlign::Center => (available_space - line_length + text_indent)
                     .scale_by(0.5)
                     .max(text_indent),
@@ -1241,6 +1253,7 @@ impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
         glyph_store: std::sync::Arc<GlyphStore>,
         text_run: &TextRun,
         font_index: usize,
+        bidi_level: Level,
     ) {
         let inline_advance = glyph_store.total_advance();
         let flags = if glyph_store.is_whitespace() {
@@ -1288,8 +1301,8 @@ impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
         let current_inline_box_identifier = self.current_inline_box_identifier();
         match self.current_line_segment.line_items.last_mut() {
             Some(LineItem::TextRun(inline_box_identifier, line_item))
-                if ifc_font_info.key == line_item.font_key &&
-                    *inline_box_identifier == current_inline_box_identifier =>
+                if *inline_box_identifier == current_inline_box_identifier &&
+                    line_item.can_merge(ifc_font_info.key, bidi_level) =>
             {
                 line_item.text.push(glyph_store);
                 return;
@@ -1306,6 +1319,7 @@ impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
                 font_metrics,
                 font_key: ifc_font_info.key,
                 text_decoration_line: self.current_inline_container_state().text_decoration_line,
+                bidi_level,
             },
         ));
     }
@@ -1436,26 +1450,9 @@ impl<'a, 'b> InlineFormattingContextState<'a, 'b> {
             assert!(!will_break);
         }
 
-        // Try to merge all TextRuns in the line.
-        let to_skip = match (
-            self.current_line.line_items.last_mut(),
-            segment_items.first_mut(),
-        ) {
-            (
-                Some(LineItem::TextRun(last_inline_box_identifier, last_line_item)),
-                Some(LineItem::TextRun(first_inline_box_identifier, first_segment_item)),
-            ) if last_line_item.font_key == first_segment_item.font_key &&
-                last_inline_box_identifier == first_inline_box_identifier =>
-            {
-                last_line_item.text.append(&mut first_segment_item.text);
-                1
-            },
-            _ => 0,
-        };
-
         self.current_line
             .line_items
-            .extend(segment_items.into_iter().skip(to_skip));
+            .extend(segment_items.into_iter());
         self.current_line.has_content |= self.current_line_segment.has_content;
 
         self.current_line_segment.reset();
@@ -1510,11 +1507,15 @@ impl InlineFormattingContext {
         text_decoration_line: TextDecorationLine,
         has_first_formatted_line: bool,
         is_single_line_text_input: bool,
+        starting_bidi_level: Level,
     ) -> Self {
         // This is to prevent a double borrow.
         let text_content: String = builder.text_segments.into_iter().collect();
         let mut font_metrics = Vec::new();
 
+        let bidi_info = BidiInfo::new(&text_content, Some(starting_bidi_level));
+        let has_right_to_left_content = bidi_info.has_rtl();
+
         let mut new_linebreaker = LineBreaker::new(text_content.as_str());
         for item in builder.inline_items.iter() {
             match &mut *item.borrow_mut() {
@@ -1524,6 +1525,7 @@ impl InlineFormattingContext {
                         &layout_context.font_context,
                         &mut new_linebreaker,
                         &mut font_metrics,
+                        &bidi_info,
                     );
                 },
                 InlineItem::StartInlineBox(identifier) => {
@@ -1537,7 +1539,12 @@ impl InlineFormattingContext {
                             Some(add_or_get_font(&font, &mut font_metrics));
                     }
                 },
-                _ => {},
+                InlineItem::Atomic(_, index_in_text, bidi_level) => {
+                    *bidi_level = bidi_info.levels[*index_in_text];
+                },
+                InlineItem::OutOfFlowAbsolutelyPositionedBox(..) |
+                InlineItem::OutOfFlowFloatBox(_) |
+                InlineItem::EndInlineBox => {},
             }
         }
 
@@ -1550,6 +1557,7 @@ impl InlineFormattingContext {
             has_first_formatted_line,
             contains_floats: builder.contains_floats,
             is_single_line_text_input,
+            has_right_to_left_content,
         }
     }
 
@@ -1630,6 +1638,7 @@ impl InlineFormattingContext {
             white_space_collapse: style_text.white_space_collapse,
             text_wrap_mode: style_text.text_wrap_mode,
             baselines: Baselines::default(),
+            has_right_to_left_content: self.has_right_to_left_content,
         };
 
         // FIXME(pcwalton): This assumes that margins never collapse through inline formatting
@@ -1654,15 +1663,16 @@ impl InlineFormattingContext {
                 },
                 InlineItem::EndInlineBox => ifc.finish_inline_box(),
                 InlineItem::TextRun(run) => run.layout_into_line_items(&mut ifc),
-                InlineItem::Atomic(atomic_formatting_context, offset_in_text) => {
+                InlineItem::Atomic(atomic_formatting_context, offset_in_text, bidi_level) => {
                     atomic_formatting_context.layout_into_line_items(
                         layout_context,
                         self,
                         &mut ifc,
                         *offset_in_text,
+                        *bidi_level,
                     );
                 },
-                InlineItem::OutOfFlowAbsolutelyPositionedBox(positioned_box) => {
+                InlineItem::OutOfFlowAbsolutelyPositionedBox(positioned_box, _) => {
                     ifc.push_line_item_to_unbreakable_segment(LineItem::AbsolutelyPositioned(
                         ifc.current_inline_box_identifier(),
                         AbsolutelyPositionedLineItem {
@@ -1907,6 +1917,7 @@ impl IndependentFormattingContext {
         inline_formatting_context: &InlineFormattingContext,
         inline_formatting_context_state: &mut InlineFormattingContextState,
         offset_in_text: usize,
+        bidi_level: Level,
     ) {
         let style = self.style();
         let container_writing_mode = inline_formatting_context_state
@@ -1986,9 +1997,13 @@ impl IndependentFormattingContext {
                     inline_formatting_context_state
                         .containing_block
                         .style
-                        .effective_writing_mode(),
-                    containing_block_for_children.effective_writing_mode(),
-                    "Mixed writing modes are not supported yet"
+                        .writing_mode
+                        .is_horizontal(),
+                    containing_block_for_children
+                        .style
+                        .writing_mode
+                        .is_horizontal(),
+                    "Mixed horizontal and vertical writing modes are not supported yet"
                 );
 
                 // This always collects for the nearest positioned ancestor even if the parent positioning
@@ -2081,6 +2096,7 @@ impl IndependentFormattingContext {
                 positioning_context: child_positioning_context,
                 baseline_offset_in_parent,
                 baseline_offset_in_item: baseline_offset,
+                bidi_level,
             },
         ));
 
@@ -2378,7 +2394,7 @@ impl<'a> ContentSizesComputation<'a> {
                     }
                 }
             },
-            InlineItem::Atomic(atomic, offset_in_text) => {
+            InlineItem::Atomic(atomic, offset_in_text, _level) => {
                 // TODO: need to handle TextWrapMode::Nowrap.
                 if !inline_formatting_context
                     .previous_character_prevents_soft_wrap_opportunity(*offset_in_text)
diff --git a/components/layout_2020/flow/inline/text_run.rs b/components/layout_2020/flow/inline/text_run.rs
index a9361de5fbe..796d07793b7 100644
--- a/components/layout_2020/flow/inline/text_run.rs
+++ b/components/layout_2020/flow/inline/text_run.rs
@@ -6,6 +6,7 @@ use std::mem;
 use std::ops::Range;
 
 use app_units::Au;
+use base::text::is_bidi_control;
 use fonts::{
     FontCacheThread, FontContext, FontRef, GlyphRun, ShapingFlags, ShapingOptions,
     LAST_RESORT_GLYPH_ADVANCE,
@@ -21,6 +22,7 @@ use style::computed_values::word_break::T as WordBreak;
 use style::properties::ComputedValues;
 use style::str::char_is_whitespace;
 use style::values::computed::OverflowWrap;
+use unicode_bidi::{BidiInfo, Level};
 use unicode_script::Script;
 use xi_unicode::linebreak_property;
 
@@ -73,6 +75,9 @@ pub(crate) struct TextRunSegment {
     #[serde(skip_serializing)]
     pub script: Script,
 
+    /// The bidi Level of this segment.
+    pub bidi_level: Level,
+
     /// The range of bytes in the parent [`super::InlineFormattingContext`]'s text content.
     pub range: Range<usize>,
 
@@ -85,10 +90,11 @@ pub(crate) struct TextRunSegment {
 }
 
 impl TextRunSegment {
-    fn new(font_index: usize, script: Script, start_offset: usize) -> Self {
+    fn new(font_index: usize, script: Script, bidi_level: Level, start_offset: usize) -> Self {
         Self {
-            script,
             font_index,
+            script,
+            bidi_level,
             range: start_offset..start_offset,
             runs: Vec::new(),
             break_at_start: false,
@@ -102,12 +108,17 @@ impl TextRunSegment {
         &mut self,
         new_font: &FontRef,
         script: Script,
+        bidi_level: Level,
         fonts: &[FontKeyAndMetrics],
     ) -> bool {
         fn is_specific(script: Script) -> bool {
             script != Script::Common && script != Script::Inherited
         }
 
+        if bidi_level != self.bidi_level {
+            return false;
+        }
+
         let current_font_key_and_metrics = &fonts[self.font_index];
         if new_font.font_key != current_font_key_and_metrics.key ||
             new_font.descriptor.pt_size != current_font_key_and_metrics.pt_size
@@ -151,6 +162,7 @@ impl TextRunSegment {
                 run.glyph_store.clone(),
                 text_run,
                 self.font_index,
+                self.bidi_level,
             );
         }
     }
@@ -198,7 +210,7 @@ impl TextRunSegment {
             text_style.overflow_wrap == OverflowWrap::Anywhere ||
             text_style.overflow_wrap == OverflowWrap::BreakWord;
 
-        let mut last_slice_end = self.range.start;
+        let mut last_slice = self.range.start..self.range.start;
         for break_index in linebreak_iter {
             if *break_index == self.range.start {
                 self.break_at_start = true;
@@ -206,12 +218,13 @@ impl TextRunSegment {
             }
 
             // Extend the slice to the next UAX#14 line break opportunity.
-            let mut slice = last_slice_end..*break_index;
+            let mut slice = last_slice.end..*break_index;
             let word = &formatting_context_text[slice.clone()];
 
             // Split off any trailing whitespace into a separate glyph run.
             let mut whitespace = slice.end..slice.end;
             let mut rev_char_indices = word.char_indices().rev().peekable();
+
             let ends_with_newline = rev_char_indices
                 .peek()
                 .map_or(false, |&(_, character)| character == '\n');
@@ -250,8 +263,8 @@ impl TextRunSegment {
                 continue;
             }
 
-            // Only advance the last_slice_end if we are not going to try to expand the slice.
-            last_slice_end = *break_index;
+            // Only advance the last slice if we are not going to try to expand the slice.
+            last_slice = slice.start..*break_index;
 
             // Push the non-whitespace part of the range.
             if !slice.is_empty() {
@@ -328,6 +341,7 @@ impl TextRun {
         font_context: &FontContext<FontCacheThread>,
         linebreaker: &mut LineBreaker,
         font_cache: &mut Vec<FontKeyAndMetrics>,
+        bidi_info: &BidiInfo,
     ) {
         let inherited_text_style = self.parent_style.get_inherited_text().clone();
         let letter_spacing = if inherited_text_style.letter_spacing.0.px() != 0. {
@@ -349,7 +363,7 @@ impl TextRun {
         let style_word_spacing: Option<Au> = specified_word_spacing.to_length().map(|l| l.into());
 
         let segments = self
-            .segment_text_by_font(formatting_context_text, font_context, font_cache)
+            .segment_text_by_font(formatting_context_text, font_context, font_cache, bidi_info)
             .into_iter()
             .map(|(mut segment, font)| {
                 let word_spacing = style_word_spacing.unwrap_or_else(|| {
@@ -360,6 +374,10 @@ impl TextRun {
                     specified_word_spacing.to_used_value(Au::from_f64_px(space_width))
                 });
 
+                let mut flags = flags.clone();
+                if segment.bidi_level.is_rtl() {
+                    flags.insert(ShapingFlags::RTL_FLAG);
+                }
                 let shaping_options = ShapingOptions {
                     letter_spacing,
                     word_spacing,
@@ -390,6 +408,7 @@ impl TextRun {
         formatting_context_text: &str,
         font_context: &FontContext<FontCacheThread>,
         font_cache: &mut Vec<FontKeyAndMetrics>,
+        bidi_info: &BidiInfo,
     ) -> Vec<(TextRunSegment, FontRef)> {
         let font_group = font_context.font_group(self.parent_style.clone_font());
         let mut current: Option<(TextRunSegment, FontRef)> = None;
@@ -416,8 +435,12 @@ impl TextRun {
 
             // If the existing segment is compatible with the character, keep going.
             let script = Script::from(character);
+            let bidi_level = bidi_info.levels[current_byte_index];
             if let Some(current) = current.as_mut() {
-                if current.0.update_if_compatible(&font, script, font_cache) {
+                if current
+                    .0
+                    .update_if_compatible(&font, script, bidi_level, font_cache)
+                {
                     continue;
                 }
             }
@@ -433,7 +456,7 @@ impl TextRun {
                 None => self.text_range.start,
             };
             let new = (
-                TextRunSegment::new(font_index, script, start_byte_index),
+                TextRunSegment::new(font_index, script, bidi_level, start_byte_index),
                 font,
             );
             if let Some(mut finished) = current.replace(new) {
@@ -449,7 +472,12 @@ impl TextRun {
             current = font_group.write().first(font_context).map(|font| {
                 let font_index = add_or_get_font(&font, font_cache);
                 (
-                    TextRunSegment::new(font_index, Script::Common, self.text_range.start),
+                    TextRunSegment::new(
+                        font_index,
+                        Script::Common,
+                        Level::ltr(),
+                        self.text_range.start,
+                    ),
                     font,
                 )
             })
@@ -496,6 +524,10 @@ fn char_does_not_change_font(character: char) -> bool {
     if character == '\u{00A0}' {
         return true;
     }
+    if is_bidi_control(character) {
+        return false;
+    }
+
     let class = linebreak_property(character);
     class == XI_LINE_BREAKING_CLASS_CM ||
         class == XI_LINE_BREAKING_CLASS_GL ||
diff --git a/components/layout_2020/flow/root.rs b/components/layout_2020/flow/root.rs
index 997392b29fd..26a1f94753d 100644
--- a/components/layout_2020/flow/root.rs
+++ b/components/layout_2020/flow/root.rs
@@ -123,7 +123,7 @@ impl BoxTree {
         #[allow(clippy::enum_variant_names)]
         enum UpdatePoint {
             AbsolutelyPositionedBlockLevelBox(ArcRefCell<BlockLevelBox>),
-            AbsolutelyPositionedInlineLevelBox(ArcRefCell<InlineItem>),
+            AbsolutelyPositionedInlineLevelBox(ArcRefCell<InlineItem>, usize),
             AbsolutelyPositionedFlexLevelBox(ArcRefCell<FlexLevelBox>),
         }
 
@@ -183,11 +183,12 @@ impl BoxTree {
                     },
                     LayoutBox::InlineBox(_) => return None,
                     LayoutBox::InlineLevel(inline_level_box) => match &*inline_level_box.borrow() {
-                        InlineItem::OutOfFlowAbsolutelyPositionedBox(_)
+                        InlineItem::OutOfFlowAbsolutelyPositionedBox(_, text_offset_index)
                             if box_style.position.is_absolutely_positioned() =>
                         {
                             UpdatePoint::AbsolutelyPositionedInlineLevelBox(
                                 inline_level_box.clone(),
+                                *text_offset_index,
                             )
                         },
                         _ => return None,
@@ -219,10 +220,14 @@ impl BoxTree {
                                 out_of_flow_absolutely_positioned_box,
                             );
                     },
-                    UpdatePoint::AbsolutelyPositionedInlineLevelBox(inline_level_box) => {
+                    UpdatePoint::AbsolutelyPositionedInlineLevelBox(
+                        inline_level_box,
+                        text_offset_index,
+                    ) => {
                         *inline_level_box.borrow_mut() =
                             InlineItem::OutOfFlowAbsolutelyPositionedBox(
                                 out_of_flow_absolutely_positioned_box,
+                                text_offset_index,
                             );
                     },
                     UpdatePoint::AbsolutelyPositionedFlexLevelBox(flex_level_box) => {