| /* |
| * Copyright 2022 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "packet_dependency.h" |
| |
| #include <algorithm> |
| #include <list> |
| #include <set> |
| |
| PacketDependency::PacketDependency(const ParentDef* root) { |
| std::map<std::string, std::set<std::string>> initial_parse_and_match_fields; |
| std::vector<std::string> available_fields; |
| CollectInitialParseAndMatchFields(root, initial_parse_and_match_fields); |
| FinalizeParseAndMatchFields(root, initial_parse_and_match_fields, available_fields); |
| } |
| |
| std::vector<std::string>& PacketDependency::GetDependencies(const std::string& packet_name) { |
| return dependencies[packet_name]; |
| } |
| |
| std::vector<std::string>& PacketDependency::GetChildrenDependencies( |
| const std::string& packet_name) { |
| return children_dependencies[packet_name]; |
| } |
| |
| std::set<std::string> PacketDependency::CollectInitialParseAndMatchFields( |
| const ParentDef* parent, |
| std::map<std::string, std::set<std::string>>& initial_parse_and_match_fields) const { |
| // Case Leaf Packet: Return all of its constraints |
| if (parent->children_.empty()) { |
| auto constraints = parent->GetAllConstraints(); |
| auto constraints_set = std::set<std::string>{}; |
| for (auto& c : constraints) { |
| constraints_set.insert(c.first); |
| } |
| return constraints_set; |
| } |
| |
| auto children_constraints = std::set<std::string>{}; |
| auto parent_constraints = parent->GetAllConstraints(); |
| auto parent_fields = parent->fields_; |
| |
| for (const auto child : parent->children_) { |
| auto constraints = CollectInitialParseAndMatchFields(child, initial_parse_and_match_fields); |
| auto child_only_constraints = std::set<std::string>{}; |
| for (auto c : constraints) { |
| // __PARENT__ |
| // c1/ c2| \c3 |
| // / | \. |
| // CH1 CH2 CH3 |
| // c4| |
| // | |
| // CH11 |
| // GetAllConstraints on leaf packet CH11 will return (C4, c1) |
| // GetAllConstraints on packet CH1 will return C1 |
| // Thus CH11 only constraint is: (C4, C1) - (C1) => (C4) |
| if (parent_constraints.find(c) == parent_constraints.end()) { |
| child_only_constraints.insert(c); |
| } |
| // If the constraint can be satisfied by the immediate parent, no need to accumulate it |
| if (parent_fields.GetField(c) != nullptr) { |
| continue; |
| } |
| // Accumulate constraints from all the children so parent packet can accurately |
| // figure out which constraints it should be getting from its parents. |
| children_constraints.insert(c); |
| } |
| // child_only_constraints contains the variables required to be passed in when calling parse |
| initial_parse_and_match_fields[child->name_] = child_only_constraints; |
| } |
| return children_constraints; |
| } |
| |
| void PacketDependency::FinalizeParseAndMatchFields( |
| const ParentDef* parent, |
| std::map<std::string, std::set<std::string>>& initial_parse_and_match_fields, |
| std::vector<std::string>& available_fields) { |
| // Root does not have any constraints on anything |
| if (parent->parent_ == nullptr) { |
| dependencies[parent->name_] = std::vector<std::string>{}; |
| children_dependencies[parent->name_] = std::vector<std::string>{}; |
| } |
| |
| // Collect the available fields, required to fix the order of pass and match vectors |
| for (auto& pf : parent->fields_) { |
| available_fields.push_back(pf->GetName()); |
| } |
| |
| auto children_constraints_to_me = std::set<std::string>{}; |
| children_dependencies[parent->name_] = std::vector<std::string>{}; |
| |
| // Accumulate direct constraints from all the children to parent |
| // __PARENT__ |
| // c1/ c2| \c3 |
| // / | \. |
| // CH1 CH2 CH3 |
| // c4| |
| // | |
| // CH11 |
| // For this case: children_constraints_to_me = (c1, c2, c3) |
| for (auto& child : parent->children_) { |
| for (auto pcons : child->parent_constraints_) { |
| children_constraints_to_me.insert(pcons.first); |
| } |
| } |
| |
| // If children constraints to the parent are (c1, c2, c3) and so far parent has |
| // fields (c1, c2) available, then parent will match its children on (c1, c2) |
| for (auto avf : available_fields) { |
| if (children_constraints_to_me.find(avf) != children_constraints_to_me.end()) { |
| auto& match_variables = children_dependencies[parent->name_]; |
| if (std::find(match_variables.begin(), match_variables.end(), avf) == match_variables.end()) { |
| match_variables.push_back(avf); |
| } |
| } |
| } |
| |
| for (auto& child : parent->children_) { |
| auto child_initial_parse_params = initial_parse_and_match_fields[child->name_]; |
| auto child_actual_parse_params = std::vector<std::string>{}; |
| |
| // Remove all the params from parse method of this child |
| // if these variables are the ones parent will match its children. |
| for (auto pcons : child->parent_constraints_) { |
| child_initial_parse_params.erase(pcons.first); |
| } |
| |
| // Store unique vars from child_initial_parse_params to child_actual_parse_params |
| // in the same order as fields are defined in the packets |
| for (auto avf : available_fields) { |
| if (child_initial_parse_params.find(avf) != child_initial_parse_params.end()) { |
| child_actual_parse_params.push_back(avf); |
| } |
| } |
| dependencies[child->name_] = child_actual_parse_params; |
| FinalizeParseAndMatchFields(child, initial_parse_and_match_fields, available_fields); |
| } |
| } |